Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
bonanova

The n-gon eats out

Question

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.

  • Upvote 1

Share this post


Link to post
Share on other sites

3 answers to this question

Recommended Posts

  • 0

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.

post-15489-0-65947200-1422718413_thumb.j

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.

  • Upvote 2

Share this post


Link to post
Share on other sites
  • 0

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.

attachicon.gifn-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.  :thumbsup:

Share this post


Link to post
Share on other sites
  • 0

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

 

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.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...