In a certain kind of tournament every player plays every oth

In a certain kind of tournament, every player plays every other player exactly once and either wins or loses. There are no ties. Define a top player to be a player who, for every other player x, either beats x or beats a player y who beats x.

First, show that there can be more than one top player. Second, prove that every n-player tournament, for n 2, has a ((at least one)) top player.

Present your proof orally (for each part).

Solution

For n = 2, we obviously have one winner in 1 game and the winner is the top player.
Assume for every group of k players playing the game there is at least one top player.
Now if we have a group of k + 1, peel off one, say q, so as to have a group of k and the one extra person, q. The group of k has at least one top player, say t. Now include q into the group and have q play the other k people.
If t beats q then since t has beaten everyone or someone who has beaten someone t didn\'t actually beat, t still satisfies the requirement of being a top player.
If q beats t, then q is automatically credited with all the players t has beaten. Let v be a person not beaten by t. If q beats all such v, we\'re finished, q is a top player. If there is one v which t hasn\'t beaten and q doesn\'t beat, then there\'s another player v0 who was beaten by t but who beats v.