wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> RANDOMIZED ICE CREAM
        
(Message started by: william wu on Aug 7^th, 2002, 8:59pm)

Title: RANDOMIZED ICE CREAM
Post by william wu on Aug 7^th, 2002, 8:59pm

A new puzzle that my friend Yosen and I recently made up. I like it, but I'm concerned that it's very unclear ... I gave it to some sharp friends and they didn't understand. I'd like suggestions on how to improve the atrocious wording. Here goes:

RANDOMIZED ICE CREAM

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! You are allowed to have one cone. You like all flavors equally, so you want to have an equal chance of picking each cone at random. However, you don't know beforehand what the total number of flavors is; you will only know that total once the supply runs out and the vendor closes the truck (boo hoo).

You can't collect all the cones before making your choice, because it wouldn't be seemly to be greedy ... so you can only hold one cone at a time. When the vendor offers you a new cone, you must either pass on it, or give away the old cone you were holding and hold the new cone. Being the little hipster that you are, you also happen to be carrying a pocket calculator which can generate random numbers from 1 to X, where X is a value you punch in. How can you choose a cone equally randomly?

If you're confused, it's kind of expected ... please feel free to post your confusions. Thanks!

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Jonathan_the_Red on Aug 8^th, 2002, 9:41am

My suggested wording:

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.

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?

-------------------

Question: in order to solve this, must we make assumptions regarding distributions over the alphabet? That is, if the vendor hands out Zanzibar Crunch, do we need to assume that there will be very few flavors after it?

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Archon on Aug 8^th, 2002, 11:31am

Quote:

must we make assumptions regarding distributions over the alphabet?

My thinking is that we don't although I don't have the answer.
I know what the general problem is, though, so perhaps describing it a few different ways will help to put people on a working path...
Essentially the problem is giving each ice cream an equal probability of being selected. A first approximation might be to say lets tell the calculator X = 2, if it comes back with 2, keep this ice cream, otherwise wait for the next one. But clearly the probabilities stack. Chance of taking the first = 1/2, chance of second = 1/2 (chance of not taking the first) * 1/2 = 1/4, third = not first * not second * 1/2, etc. And we might end up with no ice cream at all.
If I could put "infinity" into the calculator, I could give all ice creams an equally infinitely small chance of being selected. But I can't, and the chance of me having any ice cream at the end would of course also be infinitely small, so that doesn't help anyway.
Of course, I'm assuming that we want to be sure of having an ice cream at the end, so that for n ice creams, the sum of probability of choosing any ice cream = 1. That means we want each one to have a chance of 1/n. This seems impossible to me without knowing n in advance. ???
Of course, I could try to eliminate all this mathematical stuff by simply saying that the "sorting" of the ice creams alphabetically is irrelevant. I could argue that they're not sorted on density, or colour, or chemical composition, and therefore simply taking the first ice cream offered is a valid solution. I don't think this is intended, though.

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by bartleby on Aug 8^th, 2002, 11:57am

Archon,

I think you were (justifiably) confused by William's original wording, look at Jonathan's wording, it's much better.

I think the "alphabetical order" thing is a red herring... might as well say "random order."

So, you want 100% chance of keeping cone #1,
50% chance of keeping cone #2,
33% chance of keeping cone #3,
25% chance of keepign cone #4....

So it looks like:

For each cone N, generate a random number between 1 and N, and if the random number is 1, then you switch cones.

Easy-peasy?

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Jonathan_the_Red on Aug 8^th, 2002, 12:31pm

on 08/08/02 at 11:57:05, bartleby wrote:

For each cone N, generate a random number between 1 and N, and if the random number is 1, then you switch cones.

Easy-peasy?

This gives you a 0% chance of keeping the first one.

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Chronos on Aug 8^th, 2002, 12:44pm

I take it that saying "Give me a random cone" or asking the vendor how many flavors he has are not valid solutions?

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Eric Yeh on Aug 8^th, 2002, 12:55pm

Hey Will,

I just saw this problem -- pretty cool! Regarding phrasing, I think the wording is fine; I understood it well enough to solve it in a couple of mins. But then reading Jon's version did seem a little clearer... I guess one problem was that the passing on part came to late in your story (I kept stopping to try to interpret, which was a mistake; once I gave up and finished reading the whole thing, then it was relatively clear). Jon's inclusion of this together in one sentence helps.

My only other question was (briefly), whether you knew of the end of the line before or after you made your last pass decision. But once I finally stopped puzzling about that and just tried to solve it, it was clear that there was only one soln and that the q of the last pass didnt matter.

Jon,

Haha. So Bartleby made a minor error and meant if it's 1 you keep the new cone. You're such an ogre!!! ;)

General:

How do you guys find the new problems so fast?? I guess it's easy in one index, but I rarely enough come to these other forums (see William!!!) that I almost missed this one... Perhaps some general archive for new problems wuold be best?

Best,
Eric

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Jonathan_the_Red on Aug 8^th, 2002, 1:27pm

on 08/08/02 at 12:55:49, Eric Yeh wrote:

Hey Will,

Haha. So Bartleby made a minor error and meant if it's 1 you keep the new cone. You're such an ogre!!! ;)

Nope, I still don't get it. If you choose a random number from 1 to N when N=1, you're guaranteed to get 1. If Bartleby meant you keep the new cone if you get 1, that gives you a 100% chance of keeping the first one instead of 0%. What am I missing?

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Eric Yeh on Aug 8^th, 2002, 4:00pm

Oh, sorry -- I thought you were joking.

You do have to keep the first cone no matter what -- before that you have 0 cones. So if it runs out there, you'd better have kept it!

Best,
Eric

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Eric Yeh on Aug 8^th, 2002, 4:03pm

Oh -- maybe what you're missing is that that's only at the first step; you have a 100% chance of keeping it at the 1st step, but after the second cone comes out (if it comes out), you've accepted the second cone with 50% probability. So you're still holding the first cone only with 50% probability, and so on.

Best,
Eric

Title: RANDOMIZED ID NUMBERS
Post by william wu on Aug 8^th, 2002, 5:19pm

Well, you could argue that Bartleby's solution correctly handles the base case since there are no other cones to switch with when N=1, so perhaps it's implied that you keep the first cone when N=1.

Chronos: No, you can't ask the vendor for a random cone. :) Assume all the kids have duct tape across their mouths.

Jonathan's phrasing is much better, but there are still some problems. Heh, it's kinda embarrassing, but I'm confused about my own riddle. The main problem, I think, is an unclear distinction between a cone's flavor and a cone's number in the vendor's sequence.

Let's omit the words "alphabetical order" from the problem statement and see what happens. I would then argue that I could pick any flavor equally at random by simply taking the first cone offered to me, and leaving. I had no idea what flavor the first cone was. The vendor has N flavors. The first cone had a probability of 1/N of being any of those flavors. Mission accomplished!

Not the solution I intended. So that's why I put the words "alphabetical order" in there. However, I think these words are actually impotent, because you don't know the set of available flavors, and we don't want to make assumptions about flavor distributions over the alphabet. It's just a disaster.

Conclusively, I've completely reworded the problem as follows:

RANDOMIZED ID NUMBERS

Student ID cards are flowing down an assembly line, one by one. All the cards are blank, except for a unique identification number printed at the bottom. The first card to come off the line has an ID number of "1", the second card has a "2", etc. You are allowed to choose a card of your own. Since you like all numbers equally, you want to have an equal chance at picking any card. You do not know the total number of cards beforehand.

To help you pull off this feat, you have two tools: 1) a tray that can hold K cards, and 2) a random number generator.

How do you pick any card equally randomly? What is the minimum size of K?

Note: If K = total number of cards, the solution is trivial. You can move every card from the assembly line to the tray, then generate a random number between 1 and K, and finally choose the card corresponding to that random number. You can get a smaller value of K.

If anyone can think of a more creative context for this problem than ID numbers, I'd like to hear it.

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by jeremiahsmith on Aug 8^th, 2002, 6:08pm

The ID thing seems a lot clearer to me. :)

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Eric Yeh on Aug 8^th, 2002, 6:23pm

Ye, that's fine, although it loses the pizzaz of the ice cream line ;) I think the ice cream cone thing works ok wo alphabetical ordering, too -- just say hes going through a predetermined order which you do not know. Accepting the first one then isn't truly random at all. (Using the id story just gives you another predetermined order that everyone happens to know, i.e. 1, 2, 3, etc.).

Best,
Eric

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by william wu on Aug 8^th, 2002, 6:34pm

on 08/08/02 at 12:55:49, Eric Yeh wrote:

How do you guys find the new problems so fast?? I guess it's easy in one index, but I rarely enough come to these other forums (see William!!!) that I almost missed this one... Perhaps some general archive for new problems wuold be best?

I don't know how other people do it, but at the bottom of the "intro" page, there is a section called "RECENT ADDITIONS". There you can find drop-down menus listing all the riddles added since I got slashdotted on 7/24/2002. This is probably a poor location for this information. I'll consider rearranging things or something.

The problem with making a new forum for just new puzzles, is that once those puzzles get adopted, the threads will have to be moved into the regular forums (easy med hard cs microsoft), and I don't have the time to do that moving.

Argh, cafeteria is closing soon. Gotta go. Heh, I'm a prisoner to the system.

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by jeremiahsmith on Aug 8^th, 2002, 6:37pm

on 08/08/02 at 18:34:42, william wu wrote:

I don't know how other people do it...

I just go to each of the five sections, scroll all the way to the bottom, and see what puzzles I don't recognize :D

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Eric Yeh on Aug 8^th, 2002, 9:09pm

Tx for the replies guys -- hm, having to check every section just seems too much work!! Oh well, I will just have to hope that people post the fun ones to "Hard". :) ;)

Hey, is this message editor different now??

Hmm.

Best,
Eric

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by william wu on Aug 8^th, 2002, 9:32pm

Yea, I should've mentioned that. All new riddles get appended to the very bottom rows of each page. It's chronological order: top to bottom = oldest to newest.

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Eric Yeh on Aug 8^th, 2002, 9:46pm

Ye, I suppose I knew that, and I do look once in a while, but not frequently (even at the "Hard"s)... I was more wondering about puzzles that people post in the forums. But I guess it's true that this ice cream one was also in the main list.

G'nite!
Eric

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Archon on Aug 8^th, 2002, 10:07pm

I am going to deduce that K = 1, simply because in the initial statement of the problem, it was (you could hold one ice cream and see the next).
:P
As to why, I still don't have a solution. The best I have been able to do is simply invert the argument for taking the first offered and apply it to the other end of the set. Each time an item is offered, take it. The chance that this is the last item in the set for any particular item is equal (as far as you know). If it is the last item, keep it. As I said though, the reasoning is essentially the same as that for keeping the first item, so I doubt it qualifies.

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Jonathan_the_Red on Aug 9^th, 2002, 11:14am

Okay, see, as it turns out, my restatement of the problem sucked, because I didn't understand the problem myself. As I thought I understood the problem, it's unsolvable. I had thought that when the vendor handed you a cone, you needed to decide whether to keep that cone permanently or pass on it forever. Rather, he'll hand you a cone and you must decide whether to pass the new cone or the one you were already holding down the line. That makes it much easier.

So bartleby's solution works just fine. When the vendor hands you cone #N, keep your current cone with probability (N-1)/N, switch with probability 1/N.

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Eric Yeh on Aug 9^th, 2002, 11:21am

Jon,

The funny thing is, even if you didn't understand it, I still like your wording the best!!! And I definitely think it's still understandable as is!

Re: Bartleby's soln: Yes, it is pretty much correct, only leaving the very minor interpretational question of what it means to "switch" if you don't already have a cone. I agree that this is ridiculously minor, and that's why I was so surprised when I thought you were quibbling over the wording!! :)

Best,
Eric

Title: Re: New Puzzle: RANDOMIZED ICE CREAM
Post by Archon on Aug 9^th, 2002, 2:35pm

on 08/08/02 at 11:57:05, bartleby wrote:

For each cone N, generate a random number between 1 and N, and if the random number is 1, then you switch cones.
Easy-peasy?

Ah, yes, I see! Sorry, missed the nitty gritty there :)

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by igrek on Aug 12^th, 2002, 5:11pm

Isn't it similar to standard progrmming task: picking a random line from a file?
It has well-known standard solution - keep Nth line with 1/N probability.

For example, the one-line solution in Perl:

rand($.) < 1 && ($line = $_) while <>;

(from the "Perl Cookbook" by Tom Christiansen and Nathan Torkington)

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by william wu on Aug 16^th, 2002, 9:43am

on 08/12/02 at 17:11:05, igrek wrote:

Isn't it similar to standard progrmming task: picking a random line from a file?
It has well-known standard solution - keep Nth line with 1/N probability.

Yes, it is exactly like that. Nice observation.

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by Chronos on Aug 17^th, 2002, 2:43pm

You can change it back to ice cream, with one small modification. Instead of saying "...in alphabetical order", say "...in alphabetical order, starting with chocolate". This way, the strategy "choose first cone" doesn't work, because you're guaranteed to get chocolate that way. Likewise, the strategy "choose the second cone" won't work either, because then you're guaranteed to not get chocolate. And if there's yet another strategy which will work with the ice cream but not with the ID numbers, then it'll at least be fun seeing folks figure out what it is.

After all, puzzles about free ice cream are much more fun than puzzles about ID cards.

Title: Re: New Puzzle: RANDOMIZED ID NUMBERS
Post by william wu on Aug 19^th, 2002, 1:50pm

very nice fix! ok, i'll change it back to ice cream later. thanks!

Title: Re: RANDOMIZED ICE CREAM
Post by Simon_Pelletier on Apr 28^th, 2003, 7:17am

Hum, I see a problems with kids waiting in line while I type some numbers on my calculator ;D

I think a better solution would be to choose N as the number of kids in line - this way you're not only sure to get a cone (you won't pass the last cone without noticing everyone has one), but also it's a lot faster to pass cones - and we know kids don't like to wait :P

Title: Re: RANDOMIZED ICE CREAM
Post by Chronos on Apr 28^th, 2003, 10:04pm

Is it coincidence that this thread was brought back up just in time for a real free ice cream day (http://www.snopes.com/inboxer/nothing/baskin.asp)?

Title: Re: RANDOMIZED ICE CREAM
Post by c on Mar 24^th, 2012, 1:06pm

If i may, i think it's worthwhile to re-state Jonathan's observation: "I had thought that when the vendor handed you a cone, you needed to decide whether to keep that cone permanently or pass on it forever. Rather, he'll hand you a cone and you must decide whether to pass the new cone or the one you were already holding" - this is much clearly explained in the original version. The fact that your choice isn't final should be emphasized IMO.

Also, this next issue has been my fault, but another bit of info that i missed was "you will only know that total once the supply runs out and the vendor closes the truck". When i first read the version currently posted in the riddles section, i didn't register that "ALL cones need differ, EVER", so i came up with a strategy of wait until flavour comes back to chocolate, then you know how many there are and can easily generate the distributions (only this time it's from N down to 1). After all, it seems a bit silly to assume there is exactly one scoop for each flavour. Circular repetition is a more intuitive expectation, particularly if thinking there are more kids than potential flavours - which is usually the case. :-[

Title: Keith Gilabert RANDOMIZED ICE CREAM
Post by keithgilabert on May 13^th, 2012, 8:01pm

This is chaotic math. The answer lies in the flavor of the ice cream.

Good riddle,

Keith Gilabert

Title: Re: RANDOMIZED ICE CREAM
Post by yevvi on May 21^st, 2015, 9:14pm

If anyone still cares, i think we need to change back to the original wording. The new wording on the riddles page is really confusing. Nowhere it implies that i m allowed to choose between 2 cones each time. The way i understood it was that i m seeing only one cone at a time and need to decide whether to keep it or pass it on, in which case the problem has no solution. Now after reading this forum page i finally understand the problem correctly.