I’m prevailing upon the more mathematically inclined on this board to help me with this,
As far as I can tell, the number of games needed to complete any single elimination tournament is one less than the number of competitors.
E.g. The NCAA men’s basketball tournament this year will have 65 teams and 64 games. The Big 10 men’s tournament has 11 teams in it and will have 10 games.
Will that always be true and if so can someone give me some neat elegant proof to say why that is the case?
Telling people to trust me doesn’t always work.
Hard way - count the number of games at each level with the different ways byes can be arranged.
Easy way - observe that, by definition, a single elimination tournament means that everybody but the winner has lost exactly one game, and the winner has lost none. There is one loser per game, hence n-1 games.
If you have n teams, then the minimum number of matches to play (on a winners-go-through-to-next-round basis) would be n/2; where teams would be paired off with each other arbitrarily. This also assumes n is even.
But you said single elimination… if this means that the whole tournament is one big round, then surely every team has to play every other team, with the winner determined by whoever scored the most points or whatever. Then you’d have to play n*(n-1)/2 matches.
Maybe I’m confused because I know nothing about basketball… football (for example) tournaments are generally arranged with n teams being divided into groups at the start, with each group team playing all the other members of the group, and the top one or two winning teams of each group going into the next round (quarter-finals, often).
Nope. Single elimination means that if a team loses a single game, they are eliminated. (This seems unfair in something like the NCAA tourney, because the 16 initial teams in each “quadrant” (sorry, don’t recall the terminology) are assigned by their ranking, with #1 playing #16, #2 playing #15, etc. This quickly eliminates the lower-ranked teams, except for the middle ranks.)
The method you describe is close to how the NFL plays its season. A team plays every other team in its division twice, once at home, once away. It plays most of the other teams in its conference once. And it plays 0-2 cross-conference games, like Washington Redskins (NFC) against Denver Broncos (AFC). To be completely fair, the season should be 29 weeks long. But with another month of playoffs, the football season would be 8-9 months long. It’s a grueling sport that requires a lot of recoup time in the spring and summer.
There’s also double elimination, where each team has to lose twice to be eliminated from competition. The losers from the first round of play go to a losers’ tree, which is single-elimination by itself. When that tree has a winner (LW), it plays the winner of the no-loser tree (NLW). And if LW beats NLW, they have to play NLW again since NLW will have only lost once.
>>Maybe I’m confused because I know nothing about basketball… football (for example) tournaments are generally arranged with n teams being divided into groups at the start, with each group team playing all the other members of the group, and the top one or two winning teams of each group going into the next round (quarter-finals, often). <<
Oh I see, Reuben, by “football” you mean soccer, or what us Yankees refer to as soccer. At first I was confused myself unable to understand how your description refered to the NFL (or other American football leagues) playoff tiers until I realized you were painting a picture of the many “soccer” tourneys held around the world, from the World Cup to the national club championships. This seems to be a pretty ideal way of determining champions, however for something like American Football, where the recuperation time, as AWB has said, is so important and routine, it just isn’t possible. Of course, I am led to think that if somehow American football players evolve to a point where they need less time to recuperate between games, we will eventually see something like the Super Bowl series. I hope not.