The n-gon eats out

[bonanova]

n people party at a restaurant, sitting at the vertices of an n-gon-shaped dinner table. Their orders have been mixed up -- in fact, none of them have received the correct entree. Show that the table may be rotated so that at least two people are sitting in front of the correct entree.

[plasmid]

Suppose you want to find a way of distributing plates such that no one gets their own dish and there is no way of rotating the table to give two people their correct dishes.

Draw a logic grid of people at the restaurant along the horizontal axis in the order in which they're sitting around the n-gon, and whose dish they received on the vertical axis. In the figure below, if Joe had Sam's dish placed in front of him, you would fill in the green square. If you were to rotate the table, that could be represented by shifting the entire grid down (with any cells that move off the bottom of the grid wrapping back around to the top).

Since no one received their own dish, you can X out all the cells along the diagonal -- they wouldn't be allowed in an initial distribution of dishes.

Suppose Joe did receive Sam's dish. Then consider all the cells along that diagonal through the green cell running parallel to the main diagonal (the cells representing Joe getting Sam's dish, Sue getting Al's dish, Amy getting Joe's dish, etc.) Rotating the table to give Joe his dish would be shifting the entire logic grid down by two cells, so if any other cells along that diagonal had been filled, that rotation would make two dishes fall on the main diagonal so two people would get their correct dish. So if person X gets dish Y, you can't use any other cells along the diagonal through (X, Y) parallel to the main diagonal.

There are n diagonals parallel to the main diagonal (wrapping around the edges of the grid), and we crossed out the main diagonal at the outset because no one started out with their own dish, so there are (n minus 1) diagonals on which to place n dishes, which of course can't be done.

[Barcallica]

Suppose you want to find a way of distributing plates such that no one gets their own dish and there is no way of rotating the table to give two people their correct dishes.

Draw a logic grid of people at the restaurant along the horizontal axis in the order in which they're sitting around the n-gon, and whose dish they received on the vertical axis. In the figure below, if Joe had Sam's dish placed in front of him, you would fill in the green square. If you were to rotate the table, that could be represented by shifting the entire grid down (with any cells that move off the bottom of the grid wrapping back around to the top).

Since no one received their own dish, you can X out all the cells along the diagonal -- they wouldn't be allowed in an initial distribution of dishes.

n-gon table.jpg

Suppose Joe did receive Sam's dish. Then consider all the cells along that diagonal through the green cell running parallel to the main diagonal (the cells representing Joe getting Sam's dish, Sue getting Al's dish, Amy getting Joe's dish, etc.) Rotating the table to give Joe his dish would be shifting the entire logic grid down by two cells, so if any other cells along that diagonal had been filled, that rotation would make two dishes fall on the main diagonal so two people would get their correct dish. So if person X gets dish Y, you can't use any other cells along the diagonal through (X, Y) parallel to the main diagonal.

There are n diagonals parallel to the main diagonal (wrapping around the edges of the grid), and we crossed out the main diagonal at the outset because no one started out with their own dish, so there are (n minus 1) diagonals on which to place n dishes, which of course can't be done.

 

I was following the topic to see the solution to this seemingly simple but very interesting problem. 

And very nice solution by plasmid. Even school kids could understand without any trouble. 

[bonanova]

[spoiler='Nice solution indeed']I had a more complicated approach.

 

Then I looked at plasmid's graph and what it meant to move the squares up and down:

If the table makes a full rotation, each patron gets his order exactly once: there are n matches.

If any position has 0, some position must have at least 2.