Warning: it's easy to solve this puzzle if you simply misunderstand it! You might be thinking that the puzzle says X is a champion if, for every person Y, X beat Y, or beat someone who beat Y, or beat someone who beat someone who beat Y, and so on.
However, the statement of the problem does not allow this endless regression. Either X beats Y, or beats someone else who beats Y, and that's it. If the best X can do against Y is to beat U who beat V who beat Y, then X is not a champion!
Here's a bad solution by induction, under the mistaken understanding of the problem:
The statement is obviously true for N=2 players. Now suppose it's true for N players. Add one more player. We know there was at least one champion of the N players. If the old champion plays the new person and wins, he's the champion of the N+1 players, while if the new person wins, he's the champion. So no matter how many players there are, there's always at least one champion.
But read the definition carefully! If the new player Z beats the old champion Y, this does not guarantee that Z is a champion. For suppose that there is a player X that Y did not beat directly; instead, Y beat someone who beat X. Then it is possible that Z doesn't beat X, and doesn't beat someone who beat X; all we asserted was that Z beats Y. In that case, then, we cannot assert that Z is a champion. And so the induction step fails. We have not shown that there is guaranteed to be a champion for the set of N+1 people.
So, if this is what you were thinking, think again!
We will now show that, for any round robin competition, those players who have achieved the maximum score must be champions, according to the definition we are using.
Suppose that player X is one of the players who has achieved the highest number of wins in the tournament. While there may be others with the same number of wins, no one has more.
For convenience, we label W the number of wins, and L the number of losses achieved by X and remark that N=W+L+1 and that L<=W. Moreover, for every player, the number of wins and losses plus one adds up to N.
We assert that player X must be a champion. There may be other champions, but we are guaranteeing that player X is one of them.
To deny this is to assert that there is a player Y, to whom X lost, and so that any player Z who beat Y also beat X.
But this is impossible, because this means that every loss by Y is matched by a loss by X, so Y must have at least as many wins as X. But wait a minute, Y also has a win over X! That would mean that Y has a higher score than X, but this is impossible, since we chose X as one of the players with maximum score.
Thus, there can be no such player Y.
Therefore any player who achieves the maximum score in a round robin tournament is a "champion" in the sense that all other players have either been beaten by this champion, or have been beaten by someone who was beaten by this champion.
Here is an alternate proof by Yuen-Yick Kwan:
The proof is by induction on N, the number of players, which must be at least 2. For the case N = 2, either A beats B or B beats A directly, so there is always exactly one champion and the statement is correct.
Now suppose that, for any group of N or fewer players, there is always at least one champion among them, and consider the case of N+1 players.
Choose one player X arbitrarily. Divide the other players into two groups: Group A contains those who have beaten X and Group B contains those who lost to X.
If Group A is empty, then X beat all the other players, and hence we have a champion.
But if Group A is not empty, its size is less than or equal to N. So by the induction hypothesis, there is a player Y in group A who is a Group A champion, having beaten everyone in group A directly or "at second hand". But Y has also beaten player X, and player X has beaten all players in group B.
This means that Y is a champion of the entire set of N+1 players because for any player Z, either
We have thus shown that a group of N+1 players must have a champion, and hence by induction any group of players must have a champion.
Here is an proof by Yuen-Yick Kwan that there cannot be exactly two champions:
Suppose that there are two champions, whom we can call X and Y, and suppose that it is X who beats Y. Divide all the players except X into two groups: Group A, containing those who beat X, and Group B containing those who were beaten by X.
Group A cannot be empty, because otherwise Y cannot be a champion. Let Z be the champion among the players in Group A. It is easy to see that Z is actually a champion among all the players, because Z is a champion in group A, and Z beat X who beat everyone in group B.
Z and Y cannot be the same person, because Z is in group A while Y is in Group B. Thus we have shown that, given that there are two champions, there must be at least three champions. And thus there can never be exactly two champions.
Puzzle 3 was posed by Yuen-Yick Kwan. His solution is:
N Possible number of champions
_ ----------------------------
1 : 1
2 : 1
3 : 1, 3
4 : 1, 3
5 : 1, 3, 4, 5
N = 6 or more: any value from 1 to N except 2.
Yuen-Yick Kwan provided an explanation for these results as follows:
To prove the 4th point, he suggests letting A be a group of N players with K champions. Add two players X and Y, and assume the match results occur such that any player Z in A beats X who beats Y who beats Z. Then X, Y, and the original champions now constitute the K+2 champions of the set of size N+2.