math and dodgeball
Mood: cheerful
Posted on 2007-01-20 12:59:00
Tags: dodgeball math
Words: 358

As I was laying in bed last night, I realized that there was a simplification for the sum in yesterday's post. So the number of possible auctions we calculated to be 1 + 28 * sum from i=1 to 35 of (35 C i)*21^(i-1). Let's look at sum from i=1 to 35 of (35 C i)*21^(i-1) = (1/21) * sum from i=1 to 35 of (35 C i)*21^i = (1/21) * [(sum from i=0 to 35 of (35 C i)*21^i) - 1]. (this will make our argument easier)

So what is sum from i=0 to 35 of (35 C i)*21^i? We can use a combinatorial argument (counting the same thing two different ways) to simplify this. Let's say we have 35 slots, and for each slot we have a choice of the numbers 0 through 21 (inclusive). One way to count this is that we have 22 choices for each slot, and since there are 35 slots, there are 22^35 configurations. Another way to count this is to first choose how many slots will contain the number 0 - let's say there are i such slots. Well, we have (35 C i) ways to choose which slots have 0, and then there are 21 choices (since 0 isn't a possibility) for the other (35-i) slots, so this gives (35 C i)*21^(35-i). Since i can be anything from 0 to 35, there are in total sum from i=0 to 35 of (35 C i)*21^(35-i) configurations. Now, if we let j=35-i, this is the same as the sum from j=0 to 35 of (35 C (35-j))*21^j (since j will range from 0 to 35 just like i did), which is equal to the sum from j=0 to 35 of (35 C j)*21^j. This is just what we wanted!

So we have shown that the sum from j=0 to 35 of (35 C j)*21^j=22^35. Plugging this back in to our expression for the number of possible auctions, we get 1 + 28 * [(1/21) * (22^35 - 1)], which is in fact 128745650347030683120231926111609371363122697557 as desired. So I didn't have to do that ugly sum after all :-)

Dodgeball was rough - we lost 10-1 and 13 or 14-0. No major injuries, though, so that's something!

This backup was done by LJBackup.