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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.