Consider a tournament in which each contestant plays every other contestant exactly once, and one of them wins. We’ll say that a contestant $x$ is excellent if, for every other contestant $y$, either $x$ beats $y$ or there is a third contestant $z$ such that $x$ beats $z$ and $z$ beats $y$. Prove that there is at least one excellent contestant.
My attempt:
By induction.
Base case:
Two contestants. Clearly one of them wins, hence there will be an excellent contestant
Induction step:
Suppose for $n$ contestants, there will be an excellent contestant.
Now consider arbitrary $n+1$ contestants. Remove arbitrary contestant, say Bob.
Then for remaining $n$ contestants, by inductive hypothesis, there will be at least one excellent contestant, say Eva.
Now consider Eva and Bob.
Suppose Eva beats Bob. Then Eva remains an excellent contestant among $n+1$ players.
Suppose Bob beats Eva.
Since Bob wins, we have two scenarios
- Exists contestant $X$ such that Eva beats $X$ and $X$ beats Bob.
In this case, Eva will remain an excellent contestant.
- There doesn't exist contestant $X$, such that Eva beats $X$ and $X$ beats Bob.
Take arbitrary contestant $X$. We have three options
Eva beats X and X loses to Bob
Eva loses to X and X beats Bob
Eva loses to X and X loses to Bob
It can be seen that in option 1 and 3 Bob beats $X$. Now we need to consider second option.
Since Eva is an excellent contestant among $n$ players and she loses to $X$, exists $Y$ such that Eva beats $Y$ and $Y$ beats $X$.
Consider Bob and $Y$. We know that either Bob beats $Y$ or Y beats Bob.
By assumption we made above ("There doesn't exist contestant $X$, such that Eva beats $X$ and $X$ beats Bob. ") we conclude that Bob beats $Y$.
So in this case, for arbitrary contestant $X$, either Bob beats $X$, or exists $Y$ such that Bob beats $Y$ and $Y$ beats $X$. Hence Bob will be an excellent contestant.
Therefore, in any case, there will be at least one excellent contestant among $n+1$ players. (Either Eva or Bob)
$\Box$
Is it correct?