Question

Suppose \({\bf{1000}}\) people enter a chess tournament. Use a rooted tree model of the tournament to determine how many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost. (Assume there are no ties.)

Short answer

The number of games played to determine the champion is\({\bf{999}}\).

Step-by-step solution

Assuming players

Suppose \({a_1},{a_2},{a_3}, \ldots \ldots ,{a_{1000}}\) are the people in the chess tournament. Suppose \({a_4}\) is played with \({a_2}\) and \({b_1}\) is the winner. Suppose \({b_1}\) plays with \({a_3}\) and \({b_2}\) is the winner. \({b_2}\) plays with \({a_4}\) and \({a_3}\) is the winner. Repeating this argument, \({b_{98}}\) plays with \({a_{1000}}\) and \({b_{99}}\) is the winner.

Finding the champions

The process can be represented by a tree as follows:

\({b_{999}}\) is the winner of the tournament. The number of games played in the tournament is clearly the height of the tree, which is 999.

Hence, the number of games played to determine the champion is 999.