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

1. exactly one person sits at their own label and,
2. 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?

Answer 1

It is possible iff n is odd.
if n is odd we can place person 1 at seat 1, p2 @ s3, p3 @ s5 etc. it is obvious that this arrangement has the desired properties.
if n is even then in an arrangement with the needed properties the set of the offsets i-j for each pair pi @ sj would have to be the set $\{0,1,2,...,n-1\}$ modulo n. But the sum, $n(n-1)/2$, of these is not a multiple of n if n is even. At the same time, it is easy to see that for any permutation of n people this sum is 0 mod n, contradiction.

Answer 2

@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

a two-person seat swap won't change the total clockwise distance of the whole group (modulo number of persons).

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

In every possible seating order, the combined clockwise distance of persons from their seats is always the same (modulo number of persons)

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

that number is zero.

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

impossible. The total clockwise distance of the people from their seats would have to be $\sum_{n=0}^{15}n = 120$, which is 8 (nonzero) modulo 16.

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:

"Half N" multiplied by N-1 (an odd number) always leaves a nonzero remainder of N/2 when divided by N.

For odd N, the situation is different:

N-1 is then even, so $\frac{N-1}{2}$ is a whole number, and the sum will therefore always be a multiple of N, or in other words, 0 modulo N.

This means that

for odd N, such a seating order always exists.

To construct such a seating order, we can

put every person to the seat that's equal to $2\times$ their "name", modulo N.

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

    1            3
  5   2   ->   5   1
   4 3          2 4

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