Speaking of the NCAA Tournament, I’m reminded of a Puzzler once offered on NPR’s CarTalk. It goes something like this (paraphrasing liberally, as I’m not going to search their archives for the thing):
A guy in a small town somewhere decides, upon winning the Lottery, to open a bar somewhere in the Great Plains. After choosing the town — Sturgis, SD — by throwing a dart at a map, he opens his bar in late winter. Business is decent to start with, but after a few months he wants to drum up some publicity, so he decides that he’s going to hold an arm-wrestling tournament toward the end of summer. He pays a buddy of his to promote the thing on the Internet, sets up the dates, and waits for the participants to sign in. A few weeks later, he calls his buddy to find out how it’s going, and the buddy tells him:
“Man, I forgot to tell you: the dates we chose are during the Sturgis Bike Rally, when thousands of people on Harley motorcycles flock to town. We’ve got 16, 348 people signed up for the tournament! I gotta start setting it up, but first I gotta figure out how many matches that’s gonna take. That’ll take forever….”
“Wait a minute,” says the bar owner. “It’s a single-elimination tournament, right?”
“Yeah. But 16,348 people! How many matches is that?”
And without missing a beat, the bar owner tells him exactly how many matches the tournament will require. Question: How did he know, so quickly?
——-
Obviously one could figure this out with paper and pencil, dividing everything by two and counting up the matches. But in a tournament of this size, clearly this would take some time, especially for a couple of bumpkins living in Sturgis who are unaware of the Bike Rally each year! So, how does the bar owner know how immediately how many matches the tourney will require?
It has to do with the tourney itself. There are many kinds of tournaments: you can have a “Round Robin”, for example, where every entrant is guaranteed to play every other entrant at least once; or a “Double Elimination”, where each loser is placed in a “Loser’s Bracket”, with the winner of the “Loser’s Bracket” going on to the Championship and therefore every participant being able to lose twice before elimination. This, though, is a single-elimination tournament: Lose once, and you’re done. The bar owner is able to reason, then, as follows:
1. Each match will produce one loser.
2. The tournament, overall, will produce one Champion.
3. A participant can only lose one time.
Therefore:
4. The total number of matches must be equal to the total number of losers that the Tournament produces.
And then it’s simple arithmetic: since only one of the 16,348 participants can be Champion, the tourney will produce 16,347 losers — and thus take 16,347 matches to do it. QED.
So, basically, we learn that in any single-elimination tournament, the total number of games played is equal to (N – 1), where N equals the total number of participants in the tournament. Thus, the NCAA Tourney — being 64 teams — involves 63 total games. The Major League Baseball playoffs are decided by series, not individual games, but it works here too: eight teams enter the playoffs each season, so there are a total of seven playoff series held. And it even works in the NFL’s lopsided system, where four teams in the playoffs don’t even play the first round: twelve teams enter the playoffs, and eleven games later we have a Super Bowl Champion.
Thus ends the mathematical portion of Byzantium’s Shores.