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.