Pigeonhole principle: Waitress trying to match food orders by turning the round table

104 Views Asked by At

In a restaurant, a group of 16 friends takes seat on a table. The table is round, rotatable has 16 chairs placed around it symmetrically so one can easily rotate it and change meal position. 9 of the friends order the same menu called 'meal A' and the other 7 order the same menu called 'meal B'. But the waitress takes the order as a group order so she doesn't know who ordered what individually. When the order was ready, she places the meals on table randomly menu by menu. So there are 16 menus in front of the 16 people. The question here is 'At most how many people can get what they ordered by waitress rotating the table, regardless of how they are seated or how the meals are placed?' enter image description here

Each plate is 'meal A' or 'meal B' while the gray squares are chairs.

1

There are 1 best solutions below

2
On BEST ANSWER

Welcome to math.stackexchange! I trust that this question is not part of an active math contest.

Each of the $9$ meal A diners is made happy by $9$ of the rotations. Each of the $7$ meal B diners is made happy by $7$. So there are $9*9 + 7*7 = 130$ happinesses across the $16$ rotations. Therefore there is a rotation which supplies at least $130/16 = 8.2$ happinesses. I.e. some rotation makes at least $9$ diners happy.

However the same number of sad meal A folk will equal the number of sad meal B folk. So the total number of sad folk is even. Therefore the total number of happy folk is even. Since this is bounded below by $8.2$, we can always find a rotation to get at least $10$ happy diners.

Can we always do better than this? No, sometimes we can't. For example suppose that Adam is a meal A diner, and that no two of the other $8$ meal A diners sit adjacent to one another. Suppose that one of the meal As is distinguished (call it “spicy”). All the $8$ non-spicy meal As are delivered to one side of the table, and all the other 8 meals to the the other side.

It's obvious that to a first approximation, $8$ of the diners will be happy however the table is rotated. The only variations from $8$ are in the moods of Adam, and of the recipient of the spicy meal A. Sometimes they will modify the total in the same direction, sometimes the effect will cancel out. However, the overall drift from $8$ is $-2,$ $0$ or $2$ i.e. at most $2$. Therefore with this arrangement, it's not possible to have more than $10$ happy diners.

So while we might get lucky and have $16$ happy diners, the best we can guarantee is $10$.