September 1999
| At the first meal, order dishes A,B,B,C,D. At the second meal, order dishes D,E,E,F,G. At the third meal, order dishes G,H,H,I,A. Dish "A" is the only dish that appears at both the first and third meals; dish "B" is the only one that appears twice at the first meal; dish "C" is the only one that appears once at the first meal and never again; and so on. To show that ten dishes is impossible, assign each dish a triple of non-negative integers (x,y,z) if it is ordered x times at the first meal, y times at the second, and z times at the third. (x,y,z) cannot be (0,0,0) because of the stipulation that the diners have eaten all the items on the menu. The triples (x,y,z) corresponding to two different dishes must be different, or else the diners would never learn to distinguish those dishes. There are only three triples whose sum x+y+z is 1, namely (1,0,0), (0,1,0), and (0,0,1). There are only six triples whose sum x+y+z is 2, namely (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), and (0,1,1). On the nine-dish menu, these nine patterns can be used, giving a total of 1+1+1+2+2+2+2+2+2=15=5*3 dishes ordered by the five diners at three meals. (In our solution they correspond to dishes C,F,I,B,E,H,D,A,G, respectively.) But on a ten-dish menu, an additional pattern must be used, so that the total number of dishes ordered must be at least 1+1+1+2+2+2+2+2+2+3=18, too much food for five diners in three meals. |
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com