Let’s Sit Around the Table

Sometimes writing things out and trying to formalize things makes ideas and results that you would not otherwise see appear. Here is a good example of this. You have a circular table for 15 people, which has name tags at each chair for the person meant to be there. The 15 people then enter and randomly scatter to the chairs, not noticing the numbers, and each ends up in an incorrect place. Is it always possible to be able to rotate the table such that at least two people are at their correct positions?  Take some time to think about it, and then scroll below the picture.

6star-circular-table-472-dia-arne-jacobsen-fritz-hansen-1.jpg

Each person has a certain chair which they are meant to be at, and let us say that if that position is 7 seats clockwise to their current position, they have a number of 7. If it is 3 counter-clockwise, that number is -3. Of course 8 is the same as -7 because there are 15 seats, so we’ll limit the numbers from -7 to 7. We know that no one has a number of 0 because no one sat at their correct chair, so the number of possible numbers is 14 (-7 to -1 and 1 to 7). By the pigeonhole principle we know that if there are 15 people and 14 possible numbers, at least two people will have the same number. What does that mean? Well it means that there will always be a way to rotate the table so that at least 2 people are seated correctly. Now the solution seems almost trivial doesn’t it?

Advertisements

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