Let's define a tournament as a contest among $n$ players where each player plays a game agains each other player and there are no draws. Now let me define a tournament champion.
A tournament champion is a player $c$ where, for each other player $p$ in the tournament, either
- $c$ won his/her game against $p$, or
- there’s a player $q$ where $c$ won his/her game against $q$ and $q$ won his/her game against $p$.
I need to prove the following:
Prove that there are no tournaments with exactly two champions.
Before this theorem I proved this (let's call it Theorem 1):
Let T be an arbitrary tournament. Prove that if p is a player in T who lost at least one game, then at least one of the players who won against p is a tournament champion.
My attempt to prove is the following:
Let $T$ be an arbitrary tournament. We will prove that $T$ has less than or more than 2 champions. To do so, we proceed by contradiction; assume that there are exactly two champions in $T$. Let $a$ and $b$ be the only champions in $T$. Then, using a corollary of this my proof (every tournament with at least one player has at least one tournament champion) we know that our champions either both won the greatest number of games or only one of them won the greatest number of games. Therefore we proceed by cases:
Case 1: they won equal number of games. Notice, that one of the champions must win another, therefore without loss of generality assume that $a$ won $b$. Since they won equal number of games, we know that there must exist a player who won $a$, but loss $b$. Therefore using Theorem 1 we see that there must be another champion, so there are more than 2 champions, therefore we have reached contradiction.
Case 2: one of the champions won more games than another. Without loss of generality assume that $a$ won more games than $b$.
I think I understand how I can proceed in my second case to show a contradiction, but it seems that I need even more branching what I don't like, therefore I believe there is more sophisticated proof of this theorem.
Could someone please take a look at my proof and criticize my style of writing. Also I would be very grateful if you could provide any hints to a better solution if there are any.
UPDATE: Hmm, I looked a bit carefully at the problem and believe that it's easier than I thought. Assume we have only two champions in $T$. They are $a$ and $b$. We know that either $a$ won $b$ or $b$ won $a$. Without loss of generality assume that $a$ won $b$. Since $b$ is a champion, there must exist a player who won $a$, but lost $b$. Using Theorem 1 we see that there is at least one more champion in $T$. This contradicts our assumption that we have exactly two champions.
Is this correct proof or am I missing something?