Author |
Topic: RANDOMIZED ICE CREAM (Read 7324 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
RANDOMIZED ICE CREAM
« on: Aug 7th, 2002, 8:59pm » |
 Quote  Modify
|
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!
|
| « Last Edit: Nov 19th, 2002, 5:45pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
 |
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #1 on: Aug 8th, 2002, 9:41am » |
Quote Modify
|
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?
|
|
IP Logged |
My arcade cabinet
|
|
|
Archon
Newbie
Gender:
Posts: 39
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #2 on: Aug 8th, 2002, 11:31am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
bartleby
Guest
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #3 on: Aug 8th, 2002, 11:57am » |
Quote Modify
 Remove
|
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?
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #4 on: Aug 8th, 2002, 12:31pm » |
Quote Modify
|
on Aug 8th, 2002, 11:57am, 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.
|
|
IP Logged |
My arcade cabinet
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #5 on: Aug 8th, 2002, 12:44pm » |
Quote Modify
|
I take it that saying "Give me a random cone" or asking the vendor how many flavors he has are not valid solutions?
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #6 on: Aug 8th, 2002, 12:55pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #7 on: Aug 8th, 2002, 1:27pm » |
Quote Modify
|
on Aug 8th, 2002, 12:55pm, 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?
|
|
IP Logged |
My arcade cabinet
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #8 on: Aug 8th, 2002, 4:00pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #9 on: Aug 8th, 2002, 4:03pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
RANDOMIZED ID NUMBERS
« Reply #10 on: Aug 8th, 2002, 5:19pm » |
Quote Modify
|
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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #11 on: Aug 8th, 2002, 6:08pm » |
Quote Modify
|
The ID thing seems a lot clearer to me.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #12 on: Aug 8th, 2002, 6:23pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #13 on: Aug 8th, 2002, 6:34pm » |
Quote Modify
|
on Aug 8th, 2002, 12:55pm, 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.
|
| « Last Edit: Aug 8th, 2002, 6:36pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #14 on: Aug 8th, 2002, 6:37pm » |
Quote Modify
|
on Aug 8th, 2002, 6:34pm, 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
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #15 on: Aug 8th, 2002, 9:09pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #16 on: Aug 8th, 2002, 9:32pm » |
Quote Modify
|
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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #17 on: Aug 8th, 2002, 9:46pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Archon
Newbie
Gender:
Posts: 39
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #18 on: Aug 8th, 2002, 10:07pm » |
Quote Modify
|
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).
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.
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #19 on: Aug 9th, 2002, 11:14am » |
Quote Modify
|
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.
|
|
IP Logged |
My arcade cabinet
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #20 on: Aug 9th, 2002, 11:21am » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Archon
Newbie
Gender:
Posts: 39
|
|
Re: New Puzzle: RANDOMIZED ICE CREAM
« Reply #21 on: Aug 9th, 2002, 2:35pm » |
Quote Modify
|
on Aug 8th, 2002, 11:57am, 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
|
|
IP Logged |
|
|
|
igrek
Guest
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #22 on: Aug 12th, 2002, 5:11pm » |
Quote Modify
Remove
|
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)
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #23 on: Aug 16th, 2002, 9:43am » |
Quote Modify
|
on Aug 12th, 2002, 5:11pm, 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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: New Puzzle: RANDOMIZED ID NUMBERS
« Reply #24 on: Aug 17th, 2002, 2:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print