|
This problem and
its solution were invented by Michael Gottlieb in 2004, based on a story told by
Ralph Leighton.
FEYNMAN'S ORIGINAL RESTAURANT PROBLEM
has recently been deciphered from his notes.
READ MORE HERE
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) |