At a party, my wife set 24 place cards on our round table, but everybody sat down randomly, and nobody was in the right place.

My wife commented: "let's turn the table round, until at least two will be in the right place."

Can this always be so, or was it just a fluke?

I believe that even if one person sat in the right place initially, the wife would be correct.  However, I can't make a proof for this that is as elegant or understandable as Paul's of the original problem.

To prove this, I must prove that it is impossible for exactly one person to be correct in each of the 24 rotations.

Assume that there is such a case.  If the 24 guests are labelled numbers 0-23 (but not in order) then each label will be shifted clockwise n spaces from their correct places, where n is the number corresponding to the guest.

Now, we must consider this in cycle notation.*  The sum of each cycle mod 24 will be 0.  Therefore, the sum of all the numbers mod 24 is 0.  However, T(23) (the triangle number of 23) is 276, which is not divisible by 24.

Proven by contradiction.  QED


*Cycle notation is explained here in the second paragraph.

Edit: If there were 23 guests, or any other odd number, this proof does not hold!

Edited on August 10, 2005, 4:06 am

Posted by Tristan on 2005-08-10 04:04:40