Re-seating a Thousand People

Date: 6/30/96 at 13:9:32
From: The Gellman's
Subject: Different Seating Problem

I am having difficulty in solving the following problem.  Can a 
thousand people seated around a circle in seats numbered from 1 to 
1000, each person bearing one of the numbers from 1 to 1000, be re-
seated so as to preserve their (circular) order and so that no 
person's number is the same as that of the chair?

Date: 6/30/96 at 16:15:46
From: Doctor Ceeks
Subject: Re: Different Seating Problem

Suppose there were a seating arrangement where it proved impossible
to rotate the people so that no person was sitting in a seat with
the same number.

Let N(s) be the number of the person in seat s.

Note that there are 1000 possibilites for seating the people in such
a way that their circular order is preserved.

Since each of the 1000 possible seating arrangements has someone
sitting in the same numbered chair, and, for each person, only
one of the 1000 possible seating arrangements causes that person
to sit in the same numbered chair, we conclude that for each
of the 1000 possible seating arrangments, exactly one person is
sitting in the same numbered chair (by the pigeon-hole principle).

This means that N(s)-s runs through all the congruence classes
modulo 1000.  In other words, (N(s)-s)-(N(t)-t) is divisible by 1000 
if and only if s=t.

On the other hand, the sum of the number N(s)-s over all 
s = 1,...,1000 is equal to 0.

But this is impossible since modulo 1000, the sum of the numbers
1 through 1000 is equal to 500.

Therefore, no counterexample exists and it's always possible to find
a way to seat the people so that their circular order is preserved
and no person is sitting in the same numbered chair.

(Try to do this for 3 people, and you'll run into a counterexample.)

-Doctor Ceeks,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/