2003 AMC 10B Problem 15

P11-15~2 minPrint

Games & Processes Divisibility & Factors Map the objects to something easier to count

There are $100$ players in a single tennis tournament. The tournament is single elimination, meaning that a player who loses a match is eliminated. In the first round, the strongest $28$ players are given a bye, and the remaining $72$ players are paired off to play. After each round, the remaining players play in the next round. The match continues until only one player remains unbeaten. The total number of matches played is

Show solution without answering

Key insight

Every match knocks out exactly one player, and 99 players must be knocked out to leave one winner. So there are 99 matches, and 99 = 9 times 11.

Solution

Look at one match: it has one winner and one loser, and the loser is out of the tournament for good. So every match knocks out exactly one player.
The tournament ends with one unbeaten player. So $100 - 1 = 99$ players are knocked out in total.
Each knocked-out player lost exactly one match, and each match knocked out exactly one player. So the number of matches equals the number of knocked-out players: $99$ .
The byes only change when players are knocked out, not how many.
Now test $99$ against the choices: $99 = 9 \times 11$ . It is not prime, not even, and not divisible by $5$ or $7$ , but it is divisible by $11$ .

The answer is $\boxed{\textbf{(E)}\ \text{divisible by 11}}$ .

Why this works

In any knockout tournament with $n$ players there are $n - 1$ matches, because each match removes one player and all but one must be removed. When a process removes one thing per step, count the things removed instead of following the steps one by one.

Alternative approach

Follow the rounds. Round one: $72$ players make $36$ matches, and $36$ winners join the $28$ players with byes, giving $64$ players. After that: $32$ , $16$ , $8$ , $4$ , $2$ , $1$ matches. Total: $36 + 32 + 16 + 8 + 4 + 2 + 1 = 99$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Each match has exactly one loser, and a loser is eliminated and never plays again. The tournament ends when a single unbeaten player remains, so exactly $100 - 1 = 99$ players are eliminated over the whole tournament.

Matching each match to its loser is a one-to-one correspondence, so the number of matches equals the number of eliminated players: $99$ . The byes and the pairings change when players are eliminated, not how many.

Since $99 = 9 \cdot 11$ , the number of matches is divisible by $11$ (and it is odd, not prime, not divisible by $5$ or $7$ ).

The answer is $\boxed{\textbf{(E)}\ \text{divisible by 11}}$ .

Review in the AoPS books

Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)