Exercise 1.5

Question

A knock-out tournament is being held with 2 n tennis players. This means that for each
round, the winners move on to the next round and the losers are eliminated, until only
one person remains. For example, if initially there are 2 4 = 16 players, then there are
8 games in the first round, then the 8 winners move on to round 2, then the 4 winners
move on to round 3, then the 2 winners move on to round 4, the winner of which is
declared the winner of the tournament. (There are various systems for determining who
plays whom within a round, but these do not matter for this problem.)
\begin{enumerate}[label=(\alph*)]
\item How many rounds are there?
\item Count how many games in total are played, by adding up the numbers of games
played in each round.
\item Count how many games in total are played, this time by directly thinking about it
without doing almost any calculation.
\end{enumerate}
Hint: How many players need to be eliminated?

fifthist x · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item By the end of each round, half of the players participating in the round is eliminated. So, the problem reduces to finding out how many times the number of players can be halved before a single player is left.

The number of times $N$ can be divided by two is $$\log_{2}{N}$$

\item The number of games in a given round is $\frac{N_{r}}{2}$. We can sum up 
these values are for all the rounds.

\begin{equation} 
  \begin{split}
   f(N) & = \frac{N}{2} + \frac{N}{4}  + \frac{N}{8} + \dots + \frac{N}{2^{\log_{2}{N}}}\
   & =N \sum_{i=0}^{\log_{2}{N}} \frac{1}{2^{i}}\
   & =N 	imes \frac{N-1}{N}\
   & =N-1
  \end{split}
  \end{equation}

\item Tournament is over when a single player is left. Hence, $N-1$ players 
need to be eliminated. As a result of a match, exactly one player is eliminated. 
Hence, the number of matches needed to eliminate $N-1$ people is

$$ N-1 $$
\end{enumerate}

Exercise 1.5

Answers

Comments

Exercise 1.5

Answers

Comments

Add answer