Solution to September 2006 Problem

The Problem:

1. 15 chairs are equally spaced around a circular table on which are the name cards for 15 delegates. The delegates fail to notice these cards until after they have sat down and, surprisingly, no one is sitting in front of his own card. Prove that the table can be rotated so that at least two of the delegates are simultaneously correctly seated.
   
   
2. Give an example of an arrangement in which just one of the 15 delegates is correctly seated and for which no rotation correctly places more than one.

Solution.
(a) For each delegate, exactly one rotation of the table will put him in the correct seat.  Since there are 15 delegates, but only 14 nontrivial rotations, the pigeonhole principle guarantees that some rotation must accommodate two or more delegates. 

Comments.  Many solvers remarked that the same argument would work if 15 were replaced by any number n > 1 of delegates. 
            Matthew Lim reminds us that we should not be so surprised by such an arrangement — namely, that it would happen by chance that every delegate would randomly choose a seat different from the assigned seat.  In fact, there is a probability of just over 1/3 for this outcome.  For more information on this probability question you can read about it under the heading derangements.  See, for example, http://mathworld.wolfram.com/Derangement.html.

(b) The most popular solution is to place the delegates in an order that is opposite to the order of their name cards.  We shall provide two arguments why this arrangement works, one geometric and one algebraic.  After that we will give some of the other solutions that our correspondents sent us and then turn to the question of what would happen if there were n delegates instead of 15.

Geometric solution to part (b).
            We have to show that when the cards and the delegates are arranged in opposite orders, there is exactly one delegate correctly seated for each of the 15 rotations of the table.  But, this is a standard fact about the symmetries of a regular n-sided polygon, which consist of n rotations and n reflections: the rotations preserve the order of the vertices while the reflections reverse the order.  When n is odd, each reflection fixes one vertex, say vertex v, and interchanges the vertex at a distance j to the right of v with the vertex at a distance j to the left.  It remains to observe that a reflection followed by a rotation has the same effect as a single reflection — that is, the order is reversed, so there must be exactly one fixed vertex.  In the present context, that fixed position represents the delegate who is seated with the correct name card.

Algebraic solution to part (b).
            For an algebraic approach let us label our 15 delegates d = 0, 1, ... 14, and let c(d) be the number on the card that is originally in front of delegate d (so that c(d) also runs from 0 to 14).  We work "mod 15", meaning that numbers j over 15 are replaced by j – 15 (so that 15 is 0 (mod 15), 16 is 1 (mod 15), and so on).  A rotation of the table through k positions takes the position represented by c(d) to that of c(d) + k (mod 15).  Our task is to describe a permutation c(d) with the property that for each k from 0 to 14, there is exactly one d (from 0 to 14) that satisfies c(d) + k = d (mod 15).  The permutation c(d) = 15 – d puts the cards in reverse order.  It is a simple matter to check that for each value of k, the equation d = (15 – d) + k (mod 15), which reduces to

has the desired property.  Since 2d (mod 15) takes on each of the 15 possible values exactly once,  equation has exactly one solution d from 0 to 14 for each k; in other words, each rotation has exactly one position where a card is in front of the correct delegate.

Alternative solutions to part (b).
In the above algebraic solution, we can set c(d) = Md + J where M and J are numbers less than 15, and M has the property that both it and M – 1 are relatively prime to 15.  (M must be relatively prime to 15 so that Md is a permutation of the numbers from 0 to 14, while M – 1 must be relatively prime so that d = Md + J is satisfied for exactly one value of d no matter what the number J equals.)  Mir points out that that

are the only possibilities.  Since 14 is the same as –1 (mod 15), this value of M provides the popular solution we gave above (where the name cards and delegates are in opposite orders).  The other two solutions are obtained by putting the card 2d in front of delegate d, or putting the card 8d in front of delegate d (which amounts to the same thing as putting the delegate 2d in front of card d).

Solutions for when there are n delegates.
The solutions of both Bornsztein and Lim (independently) dealt with the case when n delegates sit around the table in such a way that no matter how the table is rotated, exactly one of the delegates will be seated in front of the correct card.  They show that as in the alternative solution, when n is odd, c(d) = – d is always a solution (because n – 1 and n – 2 are relatively prime to every odd number n).  It is clear that there is no solution of the form c(d) = Md + J when n is even (because either M or M – 1 will be even, and therefore not relatively prime to n).  Here is the argument both Bornsztein and Lim used to show that, more generally,

The condition (that for each k, d = c(d) + k is satisfied by exactly one d) would make both c(d) and c(d) – d permutations of {0, 1, ..., n – 1}.  Put

S = (c(0) – 0) + (c(1) – 1) + (c(2) – 2) + ... + (c(n–1) – (n–1)).