6
$\begingroup$

There is a round table with 16 seats, each seat labeled with 1 to 16 in clockwise order. Also, there are 16 people, each of whom is assigned a unique integer between 1 and 16 inclusive.

Now, the 16 people are asked to sit around the table, so that

  1. no one sits at their own label and,
  2. even if the table is rotated, there is at most one person sitting at their own label for every possible rotation of the table.

For example, a table is labeled as follows

    16 1    
  15     2  
 14       3 
13         4
12         5
 11       6 
  10     7  
    9  8    

and the people may sit as follows by taking a mirrored seat

    1 16    
  2     15  
 3       14 
4         13
5         12
 6       11 
  7     10  
    8  9    

which satisfies condition 1, but does not meet condition 2: if you rotate the table one step counterclockwise, both 1 and 9 are seated correctly.

Is this possible? Is it possible for any other value of $n$, with $n$ people and an $n$-seat table?

$\endgroup$

1 Answer 1

5
$\begingroup$

No, not for any n.
For each person there is one rotation that moves them to their number. There are as many rotations as people minus one because the 0-rotation is excluded by assumption. Therefore by pigeon-hole-principle there must be at least one rotation shared by at least two people contradicting the assumption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.