Dinner for 16
Note:
If you haven't solved the problem
Dinner for 15
, you should do this before. Dinner for 16 is an advanced version.
Trying to solve it is hopeless unless you have understood the solution of the basic version.
The problem:
Sixteen chairs are evenly placed around a circular table on which name cards are placed for
sixteen guests. The guests fail to notice these cards until after they have sat down, and
it turns out that only one person is sitting in front of his own card.
Note that there are TWO differences to Dinner for 15:
1) There are 16 guests. (This alone wouldn't make a real difference.)
2) One person is seated correctly! Therefore you can't apply the pigeonhole principle like in
Dinner for 15. (This is the real difference.)
The question:
Is it guaranteed that it is possible to rotate the table until at least two of the
guests are simultaneously correctly seated? (Just like in
Dinner for 15)
Note that if the number of guests were 15, this wouldn't be guaranteed. If they sat
at the table in reverse order for example, then every table position would result in
exactly one hit.
But now there are 16 people. And this makes a difference!
I want to see the solution.
April 28, 1995
Back to my Homepage