Collect three caps of the same team to win!

[MikeL05]

There was some NFL promotion a while ago with Coke, where you could collect bottle caps, and each had a team name. Collect 3 of the same team, and you win their t-shirt or whatever. How many bottles would you need to have a 50% or more chance of having won at least one t-shirt? Assume 32 teams and thus 32 different bottle caps.

I think I know how to figure it out, but my way would take forever. I feel like there should be a formula for something like this. Anyone got ideas on a formula?

[BruceZ]

I have deleted all of the posts having to do with my previous solution to this problem because it was no good. The whole premise of taking 1 minus the probability of 0 or 2 matches was wrong because there could be multiple instances of 2 matches which I wasn't considering. This is similar to the fun problem having to do with sets.

[LetYouDown]

I actually thought it was basically the same problem, with a smaller range but similar solution. Kind of odd that the same type of not-so-standard-question comes up twice within an hour or two. My apologies for the "Fun Problem" moniker, my creativity was at a local minima =).

[AaronBrown]

The nice thing about this promotion is they can't make one cap rare, that would just increase your chance of winning. I assume the worst case, that all caps are equally likely.

If you buy 18 cokes, you have a 49.28% chance of having three the same, the 19th brings you up to 55.09%. Although those numbers seem low, remember that the odds of three randomly chosen caps matching is 1 in 1,024, and there are 969 possible choices of 3 caps out of 19.

This is related to the birthday problem. If you pick 22 people at random, it's better than a 50/50 bet that two of them have the same birthday.

[MikeL05]

I understand the birthday problem, but that's different to me in the sense that it only requires one duplicate. So if that were the case with caps, your second cap would have a 31/32 chance of not matching, your third cap would have a 30/32 chance of not matching, etc, etc, and you could put them all together to figure out when you hit 50% or more.

With the caps, you have a 31/32 of the second cap not matching the first. Then, for the third cap, I feel like you have to come up with odds for two cases: that the first two caps match, and that the first two caps don't match. Etc etc, until it forks enough times that you go insane by the 5th cap or so.

How did you come up with 18 or 19 caps?

[AaronBrown]

You're right that the calculation is more tedious. I did it in Excel. Define a state as (number of caps of which you have zero, number of caps of which you have one, number of caps of which you have two). You start out at (32,0,0). The next state has to be (31,1,0).

The expected state after the second cap is 31/32 times (30,2,0) and 1/32 times (31,0,1). That give you an expected state of (30.0313, 1.9375, 0.0313).

When you get the third cap, there is 0.0313/32 chance that it will make your three. If it doesn't, there is 30.3013/(30.0313 + 1.9375) chance of (29.0313,2.9375,0.0313) and 1.9375/(30.0313 + 19.9375) of (30.0313,0.9375,1.0313). Multiplying that out gives (29.0919,2.8163,0.0919).

For the next cap, the probability is not 0.0919/32 of getting a triple. That is only your probability of getting at triple conditional on not having one already. So you have to multiply it by (1 - 0.0313).

That would be tedious to compute by hand, but you can copy it down in Excel easily enough. At each point, you get the probability of getting your first triple.