another misAdventure

"We are all of us living in the shadow of Manhattan."

Wednesday, November 01, 2006

Pop Quiz - Math

So, you know how bottled pop (soda, coke, insert your favorite regionalism) so often now has little contests with things printed on the cap liner? Pepsi products seem to have these things running more than half the time, if only of the "1 in 6 wins a free bottle" type.

The most recent such has had the names of the NFL football teams printed under the cap. Collect three caps with the same team and you win ... a cap!

Well, a hat. With your choice of NFL logos.

Anyway, I get myself a bottle of Diet Mountain Dew (a Pepsi product) pretty much every day. That is, on the days that I don't have two bottles. :-)

This led me to ponder a math problem: What's the expected number of caps you would need to have before collecting three of a kind. There are 32 NFL teams, so 65 caps is a guaranteed win. Ignore the caps that are not team names.

I work through this after the break ..., but I haven't got it yet. Warning! This is a math geek post.

OK, let P(n) be the probability of getting at least one group of three in n bottle caps.

P(0) = 0. P(1) = 0. P(2) = 0. P(65) = 1.

P(3) = (1/32)². To be clear, the probability of getting three of team A is (1/32)³, and then there are 32 teams so (32×(1/32)³).

OK, for n caps there are 32n possibilities if ordering is important, which it's not but I think we can factor that out by the way we do other counting (i.e. pretend order is always important). If at least three caps match then we remove those three caps from the group and there are 32(n-3) possibilities for the remaining caps. There are (n Choose 3) ways of the three matching caps appearing in the group of n. (n Choose 3) is n!÷((n-3)!×3!), or ((n)(n-1)(n-2)÷6). There are 32 different team possibilities for the matching caps, and 32n-3 possibilities for the other caps (note that this allows the other caps to also match, remember P(n) is the probability of at least 3 matching caps). All together then, P(n) = ((32(n-3)×((n×(n-1)×(n-2))÷6)×32) ÷ (32n)).

P(3) = ((32(3-3)×((3×(3-1)×(3-2))÷6)×32) ÷ (323))
     = ((320×((3×2×1)÷6)×32) ÷ (323))
     = ((1×(6÷6)×32) ÷ (323))
     = ((1×1×32) ÷ (323))
     = 32 ÷ (323)
     = 1 ÷ 322

That checks.

... and for n=65 -- um, ooops.

P(65) = ((32(65-3)×((65×(65-1)×(65-2))÷6)×32) ÷ (3265))
      = ((3262×((65×64×63)÷6)×32) ÷ (3265))
      = ((3263×((65×64×63)÷6)) ÷ (3265))
      = (((65×64×63)÷6) ÷ (322))
      = (65×64×63)÷(6 × 322)
      = (65×2×63)÷(6 × 32)
      = (65×63)÷(3 × 32)
      = not 1 . Damn!

OK, still not right. I'm sure I'm screwing up the counting due to the ordering, but I'm not sure how yet. So, this post is still a work in progress.

Anyway, I haven't figured out the expected number of caps yet, but I got a set of three with my 13th cap. Actually, my 12th and 13th caps were identical and matched one I had before.


  • I know how I'm overcounting. When I remove the three matching ones, I still allow the other ones to have all 32 values. That meanns I'm generating the same case a lot of different times.

    After more thought, I really am going to have to go with a more Stochaic solution (I think I remembered the right term). At any rate, I have to enumerate states and the probabilities to go from one state to another. I'm not sure Stochaic is the right term, though, because a state is never re-entered. At each number of bottle caps there is a distinct set of states: e.g. at 6 caps there are 5 states: no pair, 1 pair plus 4, 2 pairs plus 2, 3 pairs, three of a kind plus whatever. The last is a terminal state, and so the "whatever" doesn't matter.

    It's not so much that it's hard at this point. Just that it's tedious.

    By Blogger Tim Tjarks, at 11/02/2006 8:41 AM  

Post a Comment

<< Home