1.1.5 problem 5

(a)

By the end of each round, half of the players participating in the round are 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 $2^N$ can be divided by two is ${\text{log}}_2{2}^N$ which means the total amount of rounds in the tournament is

$$N$$

(b)

The number of games in a given round is half the number of players in that round. In the first round there are $2^{N-1}$ games, in the second $2^{N-2}$, and so on down to a single final game. We can sum up these values for all the rounds.

$$\begin{array}{cc}\begin{array}{cc}f\left(N\right)& =2^{N-1}+2^{N-2}+\cdots +2^1+2^0\\ & ={\sum }_{i=0}^{N-1}{2}^i\\ & =2^N-1\end{array}& \end{array}$$

(1.1)

(c)

Tournament is over when a single player is left. Hence, $2^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 $2^N-1$ people is

$$2^N-1$$