Question

Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people so that exactly one person receives the type of meal ordered by that person.

Answer

Solution:

Choose the one person served correctly ( $9$ ways); by symmetry say they ordered beef. The remaining meals — $2$ beef, $3$ chicken, and $3$ fish — must go to the other $8$ people ( $2$ beef, $3$ chicken, and $3$ fish orderers) with nobody matched. Track where the $2$ leftover beef meals go: to chicken or fish orderers.

If both go to the same group, say to two of the three chicken orderers ( $3 + 3 = 6$ ways counting both groups), then the third chicken orderer must receive fish, the three fish orderers must take the three chicken meals, and the two beef orderers take the remaining fish: everything is forced. If one goes to a chicken orderer and one to a fish orderer ( $3 \cdot 3 = 9$ ways), the other two chicken orderers must take fish and the other two fish orderers must take chicken, leaving one chicken and one fish meal to split between the two beef orderers ( $2$ ways).

The total is $9\,(6 + 9 \cdot 2) = 216.$

2012 AIME I Problem 3

Solution:

Problem 3 in Other Years