Counting theory: n people are sitting at a circular table with nametags...?

Question

Suppose no one sits down in their correct place. Show that it is possible to totate the table so that at least two people are sitting in the correct place.

This one's driving me nuts! I am pretty sure it has something to do with pairing the possible combinations of people and cards and the pigeon hole principle, but I'm pretty much stuck. Can anyone help me out with this one?

Answer 1

This is a pigeonhole principle. Left f(k) be the clockwise number of seats that the people need to be rotated so that person k ends up in the right seat.

Since nobody is in their right seat, f(k) is a number from 1 to n-1.

So f(1), f(2), ..., f(n) are n numbers from 1 to n-1. That means two of these numbers has to be the same.

Another solution:

Let g(k) be the number of people in their correct seats when we rotate people k places.

Then g(0) + g(1) + ... + g(n-1) = n, since everybody ends up in their correct seat in only one rotation.

But g(0)=0, because nobody is in the right place.

So:

g(1) + ... + g(n-1) = n

That means that g(i)>1 for some i.