Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/