@catahead said: This is a very long puzzle.It is possible for 16 but not for 15
bhai its solution is far too lonf see i m posting it
Suppose the result is not true. Then if all guests simultaneously move either 0,1,2,…15 places to the right (say), at most one person will be in their proper place. Because each of the sixteen guests come to their proper place at least once in this procedure, it must be the case that after each of these 16 moves, exactly one person will be in their proper seat. If we then determine, for each person the “distance” from their proper seat (all measured from the beginning position, in the direction to their right), we get each of the numbers 0,1,2,…,15 one time.
Imagine now, that one of the guests goes (to their right) to the proper seat. Then imagine that the person in that place goes (always to the right) to the proper place., and continuing, each person going to their proper place after getting “bumped” by another, until eventually one of the persons in the chain arrives at the empty chair vacated by the first guest. Each person in this chain moves their own “distance” (defined above), and the total of the distances in this chain of moves will be a multiple of 16 ( because the chain ends at the same place in which it started).
If this “chain reaction” procedure moves each guest to their proper place we can continue the arrangement. Otherwise, repeat the procedure another time, starting with one of the guests who is not properly seated. Once again, the sum of the “distances” moved in this sequence of moves is a multiple of 16. Repeat this procedure until everyone is in the proper place.
We already have observed that the sum of the “distances” for all the guests is necessarily equal to 0+1+2+….+15 = 120. On the other hand, we have also seen that it is a multiple of 16. seat (all measured from the beginning position, in the direction to their right), we get each of the numbers 0,1,2,…,15 one time.
Imagine now, that one of the guests goes (to their right) to the proper seat. Then imagine that the person in that place goes (always to the right) to the proper place., and continuing, each person going to their proper place after getting “bumped” by another, until eventually one of the persons in the chain arrives at the empty chair vacated by the first guest. Each person in this chain moves their own “distance” (defined above), and the total of the distances in this chain of moves will be a multiple of 16 ( because the chain ends at the same place in which it started).
If this “chain reaction” procedure moves each guest to their proper place we can continue the arrangement. Otherwise, repeat the procedure another time, starting with one of the guests who is not properly seated. Once again, the sum of the “distances” moved in this sequence of moves is a multiple of 16. Repeat this procedure until everyone is in the proper place.
We already have observed that the sum of the “distances” for all the guests is necessarily equal to 0+1+2+….+15 = 120. On the other hand, we have also seen that it is a multiple of 16. It follows that 120 = for some number . However, this equation has no integer solution. Consequently, our original assumption is not possible, so such a simultaneous move is possible.
The proposition need not hold if the number of people is 15 instead of 16. An example of this is shown below where the first set of numbers shows the place card numbers, the second the numbers “attached” to each guest and the third line denote each person's distance from their proper place (measured in the number of places they must move to their right). Note that these numbers are around a round table, meaning that number 14 and 0 in the first line are next to each other.
placement of guests 8 1 9 2 10 3 11 4 12 5 13 6 14 7 0
around the table
--------------------------------------------------------------------------------------
Place cards 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
--------------------------------------------------------------------------------------
each guest's distance 7 0 8 1 9 2 19 3 11 4 12 5 13 6 14
from his/her proper place
For example: guests number 8 is sitting at place card number 0, therefore he should move 7 seats to the right to get to his “correct place card (see the three green numbers in the table above). Guest number 1 is sitting at place card 1, he should move 0 seats to the right to be seated at his place card. Guest number 9 is sitting at place card number 2, he should move 8 seats to the right around the table to seated at his place card, etc. Observe that different guests have different distances, so that regardless of how they rotate as a group, only one person will be properly placed.