Track / Stage 5 / 30 of 400 #630 of 2000

Problem 630

AIME late

Combinatorics Difficulty 5.1 Find the answer

Example $1.1$ n players participate in a table tennis singles elimination tournament, how many matches need to be played to produce a champion?

Your answer

Official solution

Let $\boldsymbol{A}$ denote the set of all matches, and $B$ denote the set of all players except the champion, then $|B|=n-1$ .
Define a mapping $f$ from $A$ to $B$ as follows:
Let $a \in A$ , if player $b$ is eliminated in match $a$ , then $f(a)=b$ . It is evident that $f$ is a one-to-one correspondence from $A$ to $B$ .

By the principle of equality, $|A|=|B|=n-1$ , so it takes $n-1$ matches to determine the champion.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.