Randomized Ice Cream
Source: Wu William's Puzzle Page
Problem: A vendor is handing out free ice cream cones in alphabetical order of flavor, each cone being a different flavor. Kids are lined up at the ice cream truck, and you're first in line! The vendor will hand you ice cream cones one at a time, and you must decide whether to keep the cone or pass it on to the next kid in line. The first cone is guaranteed to be chocolate.
You like all flavors equally, so you want to randomly select a cone with each flavor having an equal chance of being chosen. Unfortunately, you don't know the total number of flavors, but being the little hipster that you are, you are carrying a pocket calculator which can generate random numbers from 1 to X, where X is a value you punch in. How can you decide which flavor to keep?
Solution:
Update (Oct 10, 2010): Solution posted by Hanumanth Rao (explained in more detail by me) in comments!
Problem: A vendor is handing out free ice cream cones in alphabetical order of flavor, each cone being a different flavor. Kids are lined up at the ice cream truck, and you're first in line! The vendor will hand you ice cream cones one at a time, and you must decide whether to keep the cone or pass it on to the next kid in line. The first cone is guaranteed to be chocolate.
You like all flavors equally, so you want to randomly select a cone with each flavor having an equal chance of being chosen. Unfortunately, you don't know the total number of flavors, but being the little hipster that you are, you are carrying a pocket calculator which can generate random numbers from 1 to X, where X is a value you punch in. How can you decide which flavor to keep?
Solution:
Update (Oct 10, 2010): Solution posted by Hanumanth Rao (explained in more detail by me) in comments!
Seems weird. It occurs to me that there can be no solution for this if one wants to select a cone with Uniformly Equal Probability. A simple proof would be :
ReplyDelete1)Assume that there are finite number of cone flavours(n).
2)The probability of selection of any particular cone should be 1/n. There is no strategy by which the first cone can be chosen with this probability.
As soon as first cone arrives keep it. When second cone arrives then keep existing cone with 2/3rd probability or keep the new cone with 1/3rd probability. Play until all cones are considered. The cone left in hand is with 1/nth probability if n cones have come along.
ReplyDeletehey , nice blog , like it ,
ReplyDeletewon’t be nice if i u can clickover to my blog page too ,
& post some suggestion
@Hanumanth Rao:
ReplyDeleteWhen n = 2 you have the first cone with 2/3 probability and second cone with probability 1/3.
@Ankush.. Hanumanth Rao's solution is correct!
ReplyDeleteConsider that you always choose between two ice creams, either the one you have, or the next one. Each step you adjust the chance for keeping or passing the cone you're holding.
Step one, take the first ice cream cone
Step two, choose with chance 1/2 to keep the cone you have, or to pass it (also chance 1/2)
Step 3, choose to keep with chance 2/3 or pass with 1/3
...
Step n, choose to keep with chance (n-1)/n, pass with 1/n
Whatever you are holding at each kth step has the same 1/k probability
Thanks Hanumanth..
crack !
ReplyDelete\m/ \m/
ReplyDelete