Lesser derangement on a round table

Question

This is a harder variant of Super-derangement on a round table.

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

exactly one person sits at their own label and,
if the table is rotated, the above condition remains true 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
    2  1    
  4      3  
 6        5 
8          7
10         9
 12       11 
  14     13  
    16 15

which satisfies condition 1, but does not meet condition 2: if you rotate the table one step counterclockwise, both 3 and 12 are seated correctly.
Is this possible? Is it possible for any other value of $n$, with $n$ people and an $n$-seat table?

Paul Panzer · Accepted Answer

Bass · Answer

@PaulPanzer's compact answer mentions all the salient points, but the actual puzzle solving (the fun part) seems to be hidden inside the "it's easy to see". :-) So, here's my way less sophisticated approach. (The end result is the same, of course.)
Since we are talking about peoples' distance from their seats, let's use the clockwise distance of a person from their own seat as the measure.
Also, since going around the table any whole number of times doesn't change anything, we'll want to do all math "modulo 16", which means that given any number we'll add or subtract 16s until we get something between 0 and 15.
Now then, when a person swaps seats with another, they go in opposite directions, so the clockwise distance of one person increases by the exact same amount (modulo 16) that the clockwise distance of the other decreases.
This means that

But we can construct all possible seating orders by using two-person swaps! This means that

and furthermore, since we can place everyone in their own seat,

This allows us to easily solve the first question: Such a seating arrangement with 16 people is

For the more general solution with N people, we can use the identity $sum_{n=0}^{N-1}n = frac{N(N-1)}{2}$ to rule out any even N:

For odd N, the situation is different:

This means that

To construct such a seating order, we can

Which gives, to pick N=5 as an example, this order:

Rotating and/or mirroring this seating order will of course also give a possible solution.

Lesser derangement on a round table

2 Answers

Add your own answers!

Ask a Question