I am practicing for my Discrete Math final and came across this question on trees in my textbook(Rosen).
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. (Assume there are no
ties.)
I am not exactly sure how to even get started with something like this using trees(although I have read the section on trees). The answer and an explanation would be nice since I don't have the solutions manual.
Best Answer
As Brian M. Scott mentioned, the correct answer is that 999 games must be played.
To get this solution using trees, let the root represent the winner and let the children of each node be the players who played a particular game, and the parent of a node be the winner of the game that they played. This is a binary tree, and so it is not too hard to see that to accommodate 1000 starting players, you will need 10 "generations" (this is where my terminology starts to get fuzzy) in addition to the root.
The remaining 24 slots can be filled with dummy players who always lose ("byes") and the most efficient method is to eliminate all of them at once, so there will be 24 players who move to the second level uncontested.
At this point you can simply count them (not by hand, of course! unless you are trying to waste time). Keep in mind that because of the byes, the first layer is a bit special. If you do all the counting correctly, you will get 999 games.