Complicated Pigeonhole Principle Homework Problem

Question

There are $n$ participants in a tournament, where $n \geq 1$. In matches in the tournament, there is a clear winner and clear loser (no ties). A participant $x$ is a "champion" if for all other participants $y$, either $x$ directly beat $y$ or $x$ directly beat some third participant $z$ who beat $y$. Prove that at least one of the $n$ participants will be a "champion".

I'm fairly certain this question requires some application of the Pigeonhole Principle, but I'm really not sure where to start. Any help would be really appreciated!

Edit: Each person will play against every other participant exactly once.

Answer 1

HINT: If $x$ is not a champion, there must be some $y$ who beats $x$. Moreover, $y$ must beat everyone whom $x$ beat, because otherwise we’d have $x$ beating some $z$ who beat $y$. Thus, $y$ must beat more people than $x$ beat: all of the ones whom $x$ beat, plus $x$. This should tell you where to look for the champion(s).

Answer 2

Hint: For each participant $x$, let $B(x)$ be the number of participants $y$ that $x$ either beats directly or for which there is a $z$ such that $x$ beats $z$ and $z$ beats $y$. Now pick an $x$ for which $B(x)$ is maximal. Prove that $x$ is a champion.

The pigeonhole principle is not used here.

Answer 3

Take a player $p$ who won a maximal number of matches -- say, $m$. I claim they're a champion.

To prove that: suppose there is a player $q$ who beat $p$. We need to show that there exists a player $r$ such that $p$ beat $r$ and $r$ beat $q$.

So, in search of a contradiction, suppose that's not the case. Then necessarily, $q$ beat all $m$ players that beat $p$. However, since $q$ ALSO beat $p$, we see that $q$ won at least $m+1$ matches -- contradicting the assumption that $p$ won the most matches of any player.