Question

Suppose 1000 people enter a chess tournament. The champion is determined in such a way that a player is eliminated after one loss and games are played until only one entrant has not lost. (Assume there are no ties.)

Required information:
The given tournament can be modeled as a full binary tree with the winner of the entire tournament as the root. Which of the following is true for the binary tree?
A. Each internal vertex represents the winner of the game played by its two siblings, and there are 1000 leaves, one for each contestant.
B. Each internal vertex represents the winner of the game played by its parents, and there are 2000 leaves, two for each contestant.
C. Each internal vertex represents the winner of the game played by its parents, and there are 1000 leaves, one for each contestant.
D. Each internal vertex represents the winner of the game played by its two children, and there are 1000 leaves, one for each contestant.
E. Each internal vertex represents the winner of the game played by its two children, and there are 2000 leaves, two for each contestant.

Answer 1

Answer: C. Each internal vertex represents the winner of the game played by its parents, and there are 1000 leaves, one for each contestant.

Step-by-step explanation: A tree is a connected undirected graph with no simple circuits. When its elements has at most 2 children, it is a Binary Tree.

The tree is formed by nodes. The topmost node is called Root and except for it, every node is connected by a direct line from exactly one other node. This type of node is called Parent.

Parent can be direct connect to a number of other nodes, which are Children and can also be internal nodes.

NOdes with no children are Leaves or external nodes.

In the Binary Tree described by the question, the number of participants is 1000, so there will be 1000 leaves. Each internal vertex repsents the winner of a game played by its parents, i.e., each is a Child, a internal node.

The right answer is alternative C.

Answer 2

Each internal vertex represents the winner of the game played by its parents, and there are 1000 leaves, one for each contestant.

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=(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=(l - 1)/(m - 1) \\\\ i=(1000 - 1)/(2 - 1) \\\\= (999)/(1) \\\\=999`