## Puzzle #110: Circular Dining Table

I am leaving for a vacation, and hence not able to post the solution to the last week’s puzzle. In the meantime, here is another puzzle, will post the answers to both next week. This puzzle is courtesy Alok Mittal, who gave this to his students in the Mathematical Circles class.

People are seated around a circular table at a restaurant. The food is placed on a circular platform in the center of the table and this circular platform can rotate. Each person ordered a different entrée, and it turns out that no one has the correct entrée in front of him. Show that it is possible to rotate the platform so that at least two people will have the correct entrée.

Please send your answers either directly on the blog site as comments, or to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.

Happy dining…with the right dish!

This entry was posted in Puzzles and tagged , . Bookmark the permalink.

### 2 Responses to Puzzle #110: Circular Dining Table

1. NARASIMHA PAI says:

1. Let N be the number of people sitting around the circular dining table. 2. Define a metric ‘d’ as the distance between a person and his entree in say the clockwise direction. For e.g. if a person’s entree is located in front of the next person sitting on his left (clockwise) then ‘d’ = 1, if it is located in front of 2nd person to his left then ‘d’ = 2 and so on. 3. Compute the ‘d’ value for each person. The minimum value of ‘d’ is 1 (not 0 since no person is facing his entree) The maximum possible value of ‘d’ is N-1 4. Since there are N persons and N-1 possible values of ‘d’, at least 2 persons will have the same ‘d’. 5. By rotating the dining table by ‘d’ in the counter clockwise direction, these 2 persons can be made to face their entree

Regards Narasimha Pai

2. Travelling Salesman says:

Let there be “n” people at the restaurant. Each of the “n” people can be served their correct entrée simply by rotating the circular platform till the person gets the correct entrée.
A person is at the distance “k” from his food if it takes “k” rotations for the food to get to that person. We can define one rotation as rotating the circular platform by one position in the anti-clockwise direction i.e. food moves one place to the right.
It is important to observe that no person can be at a distance more than n-1 from his/her food; since after n rotations the platform is back to its initial position.
Let \[ d_k \] denote the number of people at a distance k from their food.
\[ d_0 = 0 \] since no person has been given the right entrée.
Also \[ d_1 + d_2 + … + d_{n-1} = n \] since the total number of people is n.
Since n-1 non negative integers add up to n atleast one of them is > 2 i.e. \exists k : \[ d_k > 2 \]

In other words there are n people and n-1 non trivial rotations and by Pigeon Hole Principle some rotation must match atleast two people with their correct entrée. Therefore, rotating the circular platform so as to move it by k positions will have atleast 2 people in front of the food they ordered.