|
(This problem and
its solution were invented by Michael Gottlieb in 2004, based on a story told by
Ralph Leighton.)
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
<= N
(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?
Answer :
Solutions (listed by author)
Michael A. Gottlieb (html, 7k) |