Friday, November 27, 2009

How many bottle caps?

I ran across the following problem and couldn't resist. The original inspiration was a Mountain Dew promotion.

Consider the following game: Suppose you have N bottle caps, each with the name of a different sports team on the underside. You win if you draw (with replacement) three of the same team. Note that a win is impossible for less than three draws and is guaranteed by the 2N+1 draw. For n draws, the probability of having some particular set of caps (x_1, \dots, x_N), \sum_i^N x_i = n, follows a Multinomial distribution:

p(x_1, \dots, x_N) = \frac{n!}{x_1!x_2!\cdots x_N!}\left(\frac{1}{N}\right)^n

The probability of not winning by the n'th draw is the sum of all the probabilities with x_i = 0, 1, 2, i = 1, \dots, N$, and sum_i^N x_i = n. Now, permutations of the vector (x_1, \dots, x_N) are equally likely, and the number of possible non-winning vectors that have k = \max\{ n-N, 0\}, \dots, n/2 teams with two drawn caps is

{N \choose{n-k}} {{n-k}\choose{k}} = \frac{N!}{k! (n-2k)! (N-n+k)!}

Then, the probability of not winning by the n'th draw, given that there are k teams with two caps, is

p(n|k) = {N\choose{n-k}} {{n-k}\choose{k}} \frac{n!}{2^k} \left(\frac{1}{N}\right)^n

Thus, the probability of winning on the (n+1)'th draw is

p_{\rm win}(n) = \sum_{k = \max\{n-N, 0\}}^{n/2} p(n|k)\frac{k}{N}

If there are 30 teams, the chance of winning on the third draw is 0.1%. It takes about 18 draws to have a 50% chance of winning, 27 draws to have a 90% chance of winning, and 38 draws to have a 99.9% chance of winning.

Share |

Posted by Michael Culbertson at 3:36 PM

Keywords: ,

2 comments:

Derek said...

Thanks for this Michael!

November 27, 2009 8:47 PM
Josh Carr said...

Having read this, I feel a lot better about not being able to solve this problem during the few hours I whiled away tackling it with a pencil, paper, and my intuition.

December 04, 2009 8:48 PM

Post a Comment