skyking162

I threw down this challenge a few days ago: How many different ways could you fill out a 64-team NCAA bracket?

I can think of three different approaches to solving the problem, all obviously leading to the same answer. Many people would argue that it’s really the same solution looked at three different ways. I wouldn’t disagree, but having taught high school math for 2+ years, I can almost guarantee that 1/3 of a class of seniors would understand each one of these methods the first time through, but not the other two.

Approach 1: Work Forwards
Starting with the first round, there are 32 games where you must choose one of two teams. The total number of ways to make this decision is 2×2x2×2…x2 32 times — or 2^32. For each of those distinct situations, you then need to pick the 16 second round winners. There are 2^16 ways to do this. So far, there are 2^32 * 2^16 possible brackets. Bringing the third round (with eight games) into play, there are 2^32 * 2^16 * 2^8 unique brackets. Going all the way through the final game (one game, one decision) the total number of unique brackets is 2^32 * 2^16 * 2^8 * 2^4 * 2^2 * 2^1 = 2^63.

Approach 2: Work Backwards
Starting with the winner of the tournament, there are 64 options. For the runner-up, there are 32 options, because the runner-up must come from the opposite side of the bracket as the winner. For the two final-four teams that don’t make the final, there are 16 options each (these two teams must come from a different quarter (regional) of the draw than the team they lose to in the final four. So far, the total number of possible brackets is 64*32*16*16. Next, for each of the four teams that loses in the elite eight, there are 8 options, yielding a total of 64*32*16*16*8*8*8*8. Including the teams that get to, but lose in the sweet sixteen and the round of thirty-two yields a final answer of 64*32*16^2*8*^4*^8*2^16. Writing each number as a power of two yields, not surprisingly, 2^63.

Approach 3: Go Right at It
There are a total of 63 games in the NCAA tournament, as every team except the winner must lose exactly once. As such, there are 63 blanks to fill in for a bracket. For each blank, you must pick one of the two teams in the game immediately feeding into that blank. If there are two choices for each of the 63 blanks, the total number of combinations is 2×2x2x…x2 63 times, or 2^63. Didn’t see that coming, did you?

A Story About Gauss

There’s a “famous” story about Karl Frederich Gaus during his school days. His teacher asked the class to add up all the numbers between 1 and 100, thinking it was a good way to waste time (see, educational systems have always been bad.) Gauss figured out the sum almost immediately, claiming to have found a formula for adding up the numbers 1 through N, no matter what N is. The formula is N(N+1)/2 and yields 5,050 in the 1-100 example.

Why do I bring up this story? Because there are three different ways of interpreting that formula.

Interpretation One: Write all the number down on a long slip of paper and fold it in half. Each number pairs up with another number: 1/100, 2/99, 3/98, … , 50/51. Each pair adds up to 101 and there are 50 pairs. 101 x 50 = 5,050. This corresponds to the formula 100/2*101.

Interpretation Two: Take the average of all the numbers. Of course, this could require we add them all up, but it’s pretty obvious that the middle is 50.5. Then multiply by how many numbers there are: 50.5 x 100 = 5,050. This corresponds to the formula 101/2*100.

Interpretation Three: Write down the sequence once, and then a second time in reverse underneath. Each pair of values adds up to 101 and there are 100 pairs. But since we wrote the sequence twice, we have to divide by 2: 101*100/2 = 5,050.

The first explanation is what Gauss is rumored to have discovered. But either of the second two explanations is much better at explaining why the formula works for a sequence with an odd number of terms, where the midle number doesn’t pair up with another number.

Hat Tips…

… To HED for proposing the question (and answer).
… To alll math geeks out there just for being you.

Popularity: 6% [?]

This entry was posted on Saturday, April 15th, 2006 at 11:04 pm and is filed under Other Sports. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.