Solution: Tennis Tournament

Original problem: http://dharmath.blogspot.com/2010/03/tennis-tournament.html

In a tennis tournament of 100 people, each player plays every other players exactly once. There is no draw in a tennis game, one side always wins.

Given that no player loses all of his games, prove that there is a cycle of exactly 3 players. That is, there are players A,B, and C such that A defeats B, B defeats C, and C defeats A.

First Solution

First we prove that there exists a cycle of any length in the tournament. Indeed, take player A, "mark" him, and take any player that A defeats, say B, and also mark that player.. And take any player that B defeats, say C, mark him, and so on. At each turn, we are guaranteed to find a player that loses to that player. If we ever find a player that we have marked before, we obtain a cycle. But the number of marked players increases steadily while there is only a finite number of players in the tournament. Sooner or later, we will run out of players and we are guaranteed to return to a previously marked player.

If this cycle that we found has length 3, then we are done. Now we establish the following statement via induction:

A cycle of length at least 3 contains a cycle of length 3.

The base case is trivial. Now suppose we have a cycle of length $k: A_1, A_2, \cdots, A_k$ where $A_i$ beats $A_{i+1}$ and $A_k$ beats $A_1$.

If $A_1$ beats $A_{k-1}$ then we have a cycle of length 3: $A_1$ beats $A_{k-1}$ beats $A_k$ beats $A_1$.

If $A_{k-1}$ beats $A_1$ then we have a cycle of length $k-1: A_1, \cdots, A_{k-1}$ which also contains a cycle of length 3 by induction hypothesis.