Dishes and Ratings
A fast food place has N dishes on its menu that are rated from worst to best, 1 to N. 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.
How can you maximize the average total ratings of the dishes you eat in M meals (where M is less than or equal to N).
How can you maximize the average total ratings of the dishes you eat in M meals (where M is less than or equal to N).
Labels: funphysics
posted by Rajesh Lal at
7:05 AM
18 Comments:
by giveing one dish more then one name, say u have 10 dishes, and the scale goes 1 to 10, so lets us dish number 3 and dish number 8, if u were to have them b the same dish, but with different names, they would get higher rating.
just my guess
This post has been removed by the author.
I think you should assume that each dish has only one name. For simplicity name the dishes "1" to "N". I also think you should assume that each dish has a unique rating, so each possible rating is used exactly once.
Also note the hint that choosing a dish a second (or more) time might be a good way to keep the average rating high.
Think out of the box.
Take N friends with you the fast food place. Each orders a different dish, but you all share.
From then on, everyone chooses their own personal favorite.
This post has been removed by the author.
Excellent answer. But...
...I'm wrong
By Chris
Anonymous, apology accepted.
This post has been removed by the author.
This post has been removed by the author.
This post has been removed by the author.
This post has been removed by the author.
The first meal you choose will have a probable rank of (1+N)/2.
If you stick with that, expect an average rank of (1+N)/2.
The only option for the second meal is repeat the order or choose a new meal (at random). Your obvious best bet is to choose another and hope it's better. Then stick with the best one for the rest of the time. I can only say that it seems likely that the best of the two is likely give a higher rank than (1+N)/2. But I'm not sure
how to prove it.
If you don't stick then you will end up with a dilemma each time
you choose a meal "do I stop here?". If you continue to choose
random meals, then expect to get an average rank of (1+N)/2.
So my (slightly better than) guess is choose 2 meals, then stick
with the best one.
I'm equally convinced that any strategy will do.
well using Chris's idea than for any meal the chance is (n+1)/2 and then there is no strategy...but i am not 100% certain that it can be solved this way but it sure looks easy:D
I don't normally do these combinatoric/probability problems as they often end up with large amounts of data to keep track of. The reward of solving often isn't worth the effort required. But this one is interesting. I haven't really got a good tactic for cracking it.
I hope Rajesh publishes at least a clue to the solution. In fact I'd prefer only a clue if possible.
This post has been removed by the author.
I found another problem somewhere which suggests, to me, that as long as you preselect M, then you should try approx 0.34*M meals then wait for the next best one and stick with.
Post a Comment
Links to this post:
Create a Link
<< Home