Question

Suppose 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.

Answer 1

Answer: 999 games

Step-by-step explanation:

There are many ways to illustrate the rooted tree model to calculate the number of games that must be played until only one player is left who has not lost.

We could go about this manually. Though this would be somewhat tedious, I have done it and attached it to this answer. Note that when the number of players is odd, an extra game has to be played to ensure that all entrants at that round of the tournament have played at least one game at that round. Note that there is no limit on the number of games a player can play; the only condition is that a player is eliminated once the player loses.

The sum of the figures in the third column is 999.

We could also use the formula for rooted trees to calculate the number of games that would be played.

$i=\frac{l - 1}{m - 1}$

where i is the number of "internal nodes," which represents the number of games played for an "m-ary" tree, which is the number of players involved in each game and l is known as "the number of leaves," in this case, the number of players.

The number of players is 1000 and each game involves 2 players. Therefore, the number of games played, i, is given by

$i=\frac{l - 1}{m - 1} = i=\frac{1000 - 1}{2 - 1} = \frac{999}{1} =999$