Question

pts) In a round-robin tennis tournament of players, every player plays against every other

player exactly once and there is no draw. We call a player x a dominator if for every other player y

either x has beaten y directly or x has beaten some player who has beaten y. By using mathematical

induction, prove that for each integer n ≥ 2 at any round-robin tournament of n players, one can

always find a dominator.

In case 3, suppose there is no such z. This means that any player that

x has beaten a also has beaten. Now, why does that mean a is for sure

a dominator among the k+1 players? You will need to supply details rather

than just stating so. Let's think what would it require for a to be a dominator.

This means if I hand you any player y (besides a and x), then you must argue to me

that either a has beaten y or there is a player z such that a beat z and z beat y.

Why must that be true? Remember x is a dominator among the k players other

than a. So what do we know about x versus y? and how does that translate into

a versus y? (remember the observation we made earlier about x and a),

Please think a bit harder. If you would like to revise your solution you can rewrite

a solutiion and e-mail it to me by Monday noon. Please use this opportunity to think

Answer 1

For , thus is obvious. If the first player defeats the second, then he is the dominator. Else the second player is the dominator.

Let us assume that the statement is true for and is arbitrary.. Let be the dominator in the set of players .

Invoking the strong induction principle, every subset of players has a dominator, and hence a we can create an prdered tuple of dominators. Without loss of generality, we take the tuple as .

Now for , we add a new player . If defeats , then is the dominator and we are done. If not, then defeats some and let's suppose is defeated by all . The tuple then becomes , and thus we see that is the dominator. If y is not defeated as mentioned above, still he can't beat , and hence is the dominator.

Thus the statement is true for . Since was arbitrary, the statement is true for all .