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

        riddles >> easy >> Cereal Games
        
(Message started by: Benoit_Mandelbrot on Jan 22nd, 2004, 10:18am)
Title: Cereal Games
Post by Benoit_Mandelbrot on Jan 22nd, 2004, 10:18am
A cereal manufacturer inserts 5 games randomly into the boxes. Each box contains one of the 5 games. You purchase 12 boxes, so what is the chance that you will have the 5 games?
Title: Re: Cereal Games
Post by towr on Jan 22nd, 2004, 11:10am
::[hide]1324224/1953125 but there must be some better method than the quadrupple sum I used..
[/hide]::
Title: Re: Cereal Games
Post by Dudidu on Jan 22nd, 2004, 2:01pm
I get somthing else... [hide]330/1820 [approx] 0.18131 [/hide]...
I hope it's correct.
Title: Re: Cereal Games
Post by towr on Jan 22nd, 2004, 2:28pm
It's not.. ;D
I also made a simulation with 5k runs, and it gave about 2/3. So I'm pretty sure my answer is correct, or at least less far from being wrong ;)

::[hide]The chance that there's at least one game missing is slightly less than 5*(4/5)^12[approx]0.3436 (there is some overlap in the five cases where one game is certainly not in, because another might be missing as well)

Simply put we have 1 - [sum]i=14(-1)i+1Choose(5,i) [(5-i)/5]12 Which is that easier method I was looking for..
hmm.. even more simply that's: [sum]i=04(-1)iChoose(5,i) [(5-i)/5]12
[/hide]::
Title: Re: Cereal Games
Post by Dudidu on Jan 22nd, 2004, 2:49pm

on 01/22/04 at 14:28:10, towr wrote:
It's not.. ;D
I also made a simulation with 5k runs...
towr hi,
I know that it will be hard to argue with a simulation but here is my reasoning (maybe you will find them correct): [hide]Lets say that the number of the 5 games in the 12 boxs are x1, x2... x5 (each of them is non-negative). Now, [sum]i=1 to 5 xi = 12. The number of ways to choose the xi's are ( 416 ) = 1820. However, we want to have at least one instance from each game, thus,  we want that each xi [ge] 1 which can equivalently be written as [sum]i=1 to 5 xi = 7. The number of ways to choose the xi's are ( 411) = 330. [to] we get 330 / 1820[/hide].
What do you say ?
Title: Re: Cereal Games
Post by towr on Jan 22nd, 2004, 3:21pm

on 01/22/04 at 14:49:10, Dudidu wrote:
towr hi,
I know that it will be hard to argue with a simulation but
but nothing ;)
I might also have slipped something by you in editing my post..


Quote:
What do you say ?
I suppose the simplest way is to apply your method to a simpler example.

Let's take two prizes, and two boxes.
there are C(3, 1)=3 possible ways to choose x1 and x2
Now since there must be one of each, there is C(1,1)=1 way to get the desired outcome. So you would say here that the chance is 1/3 of getting both prizes if you have two boxes.
But I'm confident you see that once you have the first box and the first prize, there is a 1 in 2 chance the next box will be the other prize (and so the total probability is also 1/2).
The problem is that the ways in which you can get the different tuples of xi's aren't equally likely.

Back to the original problem. Suppose the xi's are a,b,c,d,e (adding to 12 of course) then the probability this contributes is 12!/(a!b!c!d!e!) * (1/5)12
You'll see this generally won't be the same for different tuples (a,b,c,d,e) unless these tuples are permutations of each other..
Title: Re: Cereal Games
Post by THUDandBLUNDER on Jan 22nd, 2004, 4:38pm

Quote:
What do you say ?

With 12 boxes and just 5 games, don't you think a 1 in 6 chance seems a bit low?   ;)

I get the same as towr (but I wouldn't say it's Easy).

The number of ways of getting all 5 games in 12 cereal boxes is the same as the number of ways of partitioning 12 elements into 5 non-empty sets. This number is given by S{12,5}, where S{n,k} is a Stirling Number of the Second Kind. And the 5 games can be permuted in 5! ways.

Hence total number of successes = S{12,5}*5!
Total number of ways of collecting 12 games = 512

Hence probability = S{12,5}*5!/512 = 1379400*120/244140625   = 0.678002688...

Let F(n,k) be the corresponding probability with n boxes and k games (n [smiley=eqslantgtr.gif] k [smiley=eqslantgtr.gif] 1).

Then F(n,k) = F(n-1,k) + [(1 - (1/k))n-1 * F(n-1,k-1)]
                                                           
and number of successes = i=k-1[smiley=sum.gif]i=0(-1)i * C(k,i) * (k-i)n
Title: Re: Cereal Games
Post by Benoit_Mandelbrot on Jan 23rd, 2004, 9:02am
The correct answer is [hide]33/182[/hide], but my friend won't tell me how it is.  I got this riddle from a friend.  I'm not exactly sure how this is.
Title: Re: Cereal Games
Post by towr on Jan 23rd, 2004, 10:13am

on 01/23/04 at 09:02:43, Benoit_Mandelbrot wrote:
The correct answer is [hide]33/182[/hide], but my friend won't tell me how it is.  I got this riddle from a friend.  I'm not exactly sure how this is.
That so is not the correct answer..
You can easily enough look at every case, 5^12 isn't all that much.. I suggest your friend tries it..
Title: Re: Cereal Games
Post by THUDandBLUNDER on Jan 23rd, 2004, 10:16am

Quote:
The correct answer is......I got this riddle from a friend.

Your friend must have got the puzzle from Dudidu.  ;)

This puzzle is a variant of the Coupon Collector problem and the answer is a 'well-known' result in combinatorics. Have you tried using the recurrence relation? (I derived it myself, so it must be OK!)

See The Art of Computer Programming by Knuth.

Harder puzzle: To which question is 33/182 the correct answer?  ;)
Title: Re: Cereal Games
Post by Sameer on Jan 23rd, 2004, 10:51am

on 01/23/04 at 10:16:27, THUDandBLUNDER wrote:
Your friend must have got the puzzle from Dudidu.  ;)


LOL  ;D



on 01/23/04 at 10:16:27, THUDandBLUNDER wrote:
Harder puzzle:
To which question is 33/182 the correct answer?


What is the relative prime form of 66/364?  ;D ::)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board