It’s the season for the “March Madness” college basketball tournament, and it’s also the season when people place bets on exactly what the outcome will be – not the exact scores, if I understand correctly, but which teams will win each game. If you didn’t already know, MM is a single-elimination contest among 64 different excellent varsity college basketball teams; one loss and your team is out. If your team wins every single game it plays (six games), your team is the national champion.
Inspired by seeing an office pool and a recent book on how some gamblers ‘fix’ sporting events all over the world in order to win more money, I got to wondering how difficult it would be for someone like me who knows almost nothing about college basketball to predict the exact outcome of the tournament. Not just which team will takes the ultimate trophy, but which team will lose and which team will win, in all of the many individual matchups? (Forget predicting point spreads — you need a lot of inside knowledge to get that right, and that’s precisely the sort of thing that gamblers pay referees and players to cheat on.)
My question is simpler: exactly how many combinations and permutations will there be of who will be the winners of each and every single game of any year’s March Madness?
Thinking that tackling the actual problem would initially be too difficult, I decided to try a simpler question. What if there are only two teams? Obviously, only 2 outcomes: either team A wins, or team B wins, end of story.
How about if there are four teams? (Note: for there to be no “byes” and for this to be single-elimination, this column only considers cases where there are 2^n teams: 2, 4, 8, 16, 32, 64, and so on.) The answer was not obvious, so I drew a little diagram of all possible cases, which I roughly reproduce with MSPaint, here:
I called the teams A, B, C, and D. As you can see, there are exactly two ways that team A can win, two ways that team B can win, two ways for team C to be victorious, and two ways for team D to win – a grand total of 8 possible outcomes.
Another way of thinking of this is NOT to list and count all of the possible outcomes, but to figure out a way of counting WITHOUT counting.
I looked at the same situation and realized that there were two outcomes possible for each and every game, and you can multiply the number of possibilities at each node (location where two branches meet) branch by the number of possibilities at each other branch to get the same result, as you see here:
If there are eight teams, there are seven nodes, as you can see here:
Which works out to 2 x 2 x 2 x 2 x 2 x 2 x 2 outcomes, or 2^7. Notice that 7, the exponent, is one less than 8, the number of teams, just as 3 (the exponent in the previous case) was one less than 4, the number of teams. Does this pattern continue?
Yes, it does! I took my previous drawing and extended it to 16 teams, mostly by copying and pasting, which doubled the number of nodes, then I added one more at the very bottom. So this gave me 7 x 2 + 1, or 15 different nodes, or 2^15 different possible outcomes, and, as before, 15 is one less than 16.
Consequently, continuing the same pattern, if there were only 32 teams in March Madness, then there would be 2^31 different possible outcomes. In the current, real-world March Madness, there are 64 teams, so there must be 2^63 possible ways that the entire tournament could come out. (Which, parenthetically, is the number of grains of rice on the very last square of the mythical rice-doubling-award that was legendarily asked by the inventor of the game of chess…)
Is that a large number? Heck, yes! In fact, the numbers get very quickly very huge.
2^1 = 2
2^3 = 8
2^7 = 128 (over a hundred)
2^15 = 32,768 (over thirty thousand)
2^31 = 2,147,483,648 (over two billion)
2^63 = about 9,223,372,036,854,780,000 (my computer can’t exactly count that high, but it’s over 9 quintillion!)
If you were counting the seconds since the Big Bang, which apparently occurred over 14 Billion years ago, you would be nowhere near that result. You would in fact need roughly twenty lifetimes of the entire universe to count that number of seconds…
March Madness indeed. And, knowing as little as I do about which teams are better or worse, I would be indeed mad to try to bet on the outcome. What about you?