Feynman's restaurant problem

Atwood's machine ] bag of marbles ] balance moon stone ] ball up/down ] bead parabola accelerometer ] boat anchor lake ] boat time ] bobbin on incline ] bosun's chair ] bouncing ball ] bowling ball rolling ] bug on band ] bursting shell ] falling chain ] [ Feynman's restaurant problem ] five pills ] flying cable ] forced pendulum ] gold mountain ] half pills ] hallway pole ] impelled rod ] inelastic relativistic collision ] infinite pulleys ] mass on an incline ] maximum angle of deflection ] packs of shirts ] particle in bowl ] particle in cone ] particle on sphere ] particle points parabola ] pile of bricks ] pion muon neutrino ] piston ramp spring ] plank weight trough ] rocket vs. jet ] roll without slipping ] rough inclined plane ] shooting marbles ] speedometer test ] three balls ] three logs ] turntable cart ] two rolling balls ] wheel and block ] whirling pendulum ] worlds fair ornament ]

service

(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 (MD) meals, in order to maximize the average total ratings of the dishes consumed?

Answer


Solutions (listed by author)

Michael A. Gottlieb (html, 7k)

 

Copyright 2000-2013 Michael A. Gottlieb. All rights reserved.