Problem #59 MEDIUM
The Chess Tournament Bracket
Scenario Combinatorics Logic Pattern Recognition
Problem Statement
The all-India inter-school chess championship is held every year in Chennai. This year, 64 students have registered to compete.
The tournament director, Mrs. Radha, is explaining the format to the school principals gathered in the auditorium.
'We use a single-elimination format,' she says. 'Every round, players are paired up. The winner advances. The loser is eliminated. No draws, no byes, no second chances.'
One of the principals, a retired mathematics professor, raises his hand. 'So how many total games will be played across the entire tournament?' he asks.
'And,' adds another principal, 'how many rounds will it take before we have a champion?'
Mrs. Radha smiles at the retired professor. 'You tell me,' she says.
In a single-elimination tournament with 64 players, how many total games are played? How many rounds does it take? Now generalise for any number of players n that is a power of 2.
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
63 total games are played across 6 rounds. The elegant proof: each game eliminates exactly 1 player, and 63 players must be eliminated to crown 1 champion from 64. General formula: n players require exactly n-1 games and log₂(n) rounds.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
There are two ways to count: the round-by-round method and the elegant elimination argument. The elimination argument is more powerful because it works for any number of players, not just powers of 2.
Step 1: Round-by-round: Round 1 — 64 players → 32 games → 32 winners. Round 2 — 32 players → 16 games. Round 3 — 16 → 8 games. Round 4 — 8 → 4 games. Round 5 — 4 → 2 games. Round 6 (Final) — 2 → 1 game.
Step 2: Total games = 32+16+8+4+2+1 = 63. This is a geometric series: 32(1 - (1/2)^6)/(1-1/2) = 63.
Step 3: Elegant argument: In a single-elimination tournament, every game produces exactly 1 loser. Every player except the champion loses exactly once. So total losers = 63. Total games = total losers = 63.
Step 4: This argument works for ANY number of players, not just powers of 2: a tournament with n players always requires exactly n-1 games, regardless of the bracket structure.
Step 5: Number of rounds (for powers of 2): each round halves the field. Starting with 64 = 2^6, we need 6 halvings to reach 1. Rounds = log₂(64) = 6.
Step 6: General formula: n players → n-1 total games, log₂(n) rounds (when n is a power of 2).
Key Insight:
The elimination argument is one of the most elegant counting techniques in combinatorics. Instead of counting forward (how many games per round?), count backward (how many players must be eliminated?). Since each game eliminates exactly one player and exactly n-1 must be eliminated, the answer is immediate: n-1 games, always.