Skip to main content

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!

Comments

  1. 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 :
    1)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.

    ReplyDelete
  2. 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.

    ReplyDelete
  3. hey , nice blog , like it ,
    won’t be nice if i u can clickover to my blog page too ,
    & post some suggestion

    ReplyDelete
  4. @Hanumanth Rao:
    When n = 2 you have the first cone with 2/3 probability and second cone with probability 1/3.

    ReplyDelete
  5. @Ankush.. Hanumanth Rao's solution is correct!

    Consider 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..

    ReplyDelete

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?