display | more...
Answer to old chestnut: foreign restaurant:

There were nine items on the menu.

In the total of 15 meals ordered, they ordered three dishes twice in the same night (one each night, identifying them immediately), ordered three dishes twice on different nights (one in each of the three combinations of two nights), and ordered three dishes only once each (each on a different night).

One possible scheme for ordering dishes is as follows:

First night: A A D E G
Second night: B B D F H
Third night: C C E F I

If there had been ten dishes on the menu, then in order for them to have ordered each one once, they could only have ordered a maximum of five dishes twice, so there would be at least five dishes they only ordered once. But since there were only three nights, at least two of those dishes must have been ordered the same night, and they wouldn't have been able to distinguish them. Nine is the maximum.

Note: If there were fewer items on the menu, to get valid schemes for identifying each dish from the one above, replace some items by the item already ordered multiple times that night -- so if there were eight items, you might replace I with a third C the third night.

Note: In some variations of the problem, it is not required that the friends have tried each dish, only that they can identify each of them; in this case, they can identify exactly one more dish which they don't order at all these three nights.

In the general case, determine how many dishes may be ordered just once (equal to the number of nights they ate together), how many dishes may be ordered exactly twice (one set, which they ordered twice the same night, is equal to the number of nights they ate together; another set, ordered on different nights, is equal to the number of combinations of two different nights), how many dishes may be ordered exactly three times, etc. Add up the total number of meals needed to be ordered to identify these dishes until you reach the total number of meals they actually ordered (friends times nights). If this comes out evenly like in this problem, you should have your answer; if it comes out unevenly, make a test assignment and try to choose ordering patterns as evenly distributed as possible, and if necessary fill extra dish slots with duplicates as suggested above.

Log in or register to write something here or to contact authors.