Question

24. Suppose that each player in a tennis tournament( like the binary-tree tournament in Example 1) brings a new can of tennis balls. One can is used in each match and the other can is taken by the match’s winner along to the next round. Use this fact to show that a tennis tournament with n entrants has n − 1 matches.

Answer 1

Method is very simple . We can represent the situation by binary tree with n leaf nodes representing n players.

Now the match between two players will be represented by an internal node whose two children will be the participating players.

We can observe that in this situation, we have a complete binary tree with n leaf nodes, and internal node represent the matches whose winner goes upward and finally the root node represent the winner.

So, total number of matches = total number of internal nodes = n-1

Since, complete binary tree with n leaf nodes have n-1 internal nodes.

Hence there are n-1 matches.

Please comment for any clarification .