Solution to Puzzle #110: Circular Dining Table

This was a relatively easy puzzle and many people sent a correct answer. That included Siddhartha Goel, Suman Saraf, Pratik Poddar, Traveling Salesman (which I believe is a nick name), Narsimha Pai and Salil Panikkaveettil.

The puzzle used a popular and intuitive principle called the Pigeon Hole principle. At a simplistic level, it states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. This surprisingly simple principle is used very widely and finds many applications.

I am taking the liberty of reproducing Siddhartha Goel’s answer for this puzzle:

1) n – eaters, n – entrees

2) no duplicate entrees etc: each user has a 1:1 match with 1 entree

3) A permutation can be rotated ‘n’ times and a total of n matches (eater – entree) will happen in ‘n’ rotations

4) If in 1 permutation we have 0 matches => in remaining (n-1) rotations of that permutation there needs to be a total of n matches => at least 1 rotation of the permutation will have at least 2 matches… (0, 1, 1, 1, … 2)…

For people, who are interested in a more detailed treatment of Pigeon Hole principle, please refer to https://en.wikipedia.org/wiki/Pigeonhole_principle

Hope you enjoyed the puzzle!

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s