(This problem and
its solution were invented by Michael Gottlieb in 2004, based on a story told by
Richard Feynman and Ralph
Leighton had a hard time at restaurants deciding whether to order
the best dish they had tried so far or something new, which -
who knows - might be even better. So, naturally,
they decided to formalize this as a mathematical problem:
Assume that a restaurant has N dishes on its menu that are rated from worst to
best, 1 to N (according to your personal preferences). You, however, don't know the ratings of the dishes,
and when you try a new dish, all you learn is
whether it is the best (highest rated)
dish you have tried so far, or not. Each time you eat a meal at the restaurant you either order a new dish or you order the best dish you have tried so far.
Your goal is to maximize the average total ratings of the dishes you eat in M meals
(where M is less than or equal to N).
The average total ratings in a sequence of meals that includes n "new"
dishes and b "best so far" dishes can be no higher
than the average total ratings in the sequence having all n "new"
dishes followed by all b "best so far" dishes. Thus a successful
strategy requires you to order some number of new dishes and thereafter only
order the best dish so far. The problem then reduces to the following:
Given N (dishes on the menu) and M
(meals to be eaten at the restaurant), how many new dishes D should you try
before switching to ordering the best of them for all the remaining (M–D) meals, in order to
maximize the average total ratings of the dishes consumed?
Solutions (listed by author)
Michael A. Gottlieb (html, 7k)