A tournament was played round-robin: each pair of players played a match where one defeated the other. Prove that there was a player for which every other player either lost to them or lost to someone who lost to them.
Formally: Prove that if you direct the edges of a complete undirected graph, then there exists a vertex from which every vertex is reachable by a directed path of length at most 2.
Assume the converse. That is, for any player $A$ there is another player $f(A)$ who beat $A$ and who beat at least those players beaten by $A$.
Then $f(f(A))$ must have beaten $A$, and must have beaten at least those players beaten by $A$. By induction we generate an unlimited chain of players $f^i(A)$, who each beat $A$.
But as the number of players is finite the chain must contain a cycle, and therefore a player who has beaten himself - a contradiction.
Suppose a tournament of $n$ players have a dominant player (this is trivially true for $n=1,2,3$). We now try to prove that a tournament of $n+1$ players also have a dominant player, which is either the previous dominant player or the new player himself.
Let's call the previous dominant player $D$ and the new player $N$.
Suppose $D$ beats $N$. Then $D$ is still a dominant player in the tournament of $n+1$ players.
Then now we can assume that $N$ beats $D$.
Now, if there is a person $H_1$ such that $D$ beats $H_1$ and $H_1$ beats $N$, then $D$ is still a dominant player, since it dominates all other player, including the new player $N$.
So this means now we can assume that $N$ beats everyone that was beaten by $D$.
This means everyone that was dominated by $D$ will be dominated by $N$ also. And since $N$ beats $D$, $N$ dominates the whole tournament, making $N$ the new dominant player, proving the claim. =)
More formally, we'll represent the players as vertices in a graph, and the matches outcome as directed edges between those vertices.
First, some notations:
Let $G = \{V, E\}, V = \{v_1, v_2, \ldots, v_n\}, E = \{(v_i, v_j) | \text{player }i\text{ beats player }j\}$
Let $d_G(v_i, v_j)$ be the shortest path length from $v_i$ to $v_j$ in $G$.
Let $s_G(v)$ be the maximum distance from $v$ in $G$ (formally: $s_G(v) = max(\{d_G(v, v_i)\ |\ \forall v_i \in G\})$)
To be proven:
In any graph $G$, $min(\{s_G(v)\ |\ v\in G\}) \leq 2$
We'll prove by induction.
Let $n = |V|$, which is the number of vertices in $G$.
For $n=1,2,3$, it's trivial, since the longest path in such graphs will be 2.
Assume the property holds for $|V| = n$. Now we are trying to prove that it also holds for $|V| = n+1$.
Let $G$ be such that $|V| = n$. By induction hypothesis, there is a vertex with distance at most 2 to any other vertices. Without loss of generalization, $s_G(v_1) \leq 2$
We want to add one new vertex $v_{n+1}$ to $G$ and prove that the property still holds.
Now, if $s_G(v_1) = 1$ (i.e., player $1$ beats all other players in $G$), we have two cases:
$(v_{n+1}, v_1) \in E$ (i.e., player $n+1$ beats player $1$)
This implies $s_G(v_{n+1}) = 2$, so the property still holds.
$(v_1, v_{n+1}) \in E$ (i.e., player $1$ beats player $n+1$)
This implies $s_G(v_1) = 1$, so the property still holds.
So we can now assume that $s_G(v_1) = 2$
If $(v_1, v_{n+1}) \in E$, then we still have $s_G(v_1) = 2$ and the property still holds.
So we can now assume that $(v_{n+1}, v_1) \in E$
Let $H_1, H_2$ denotes, respectively, the vertices of distance 1 and distance 2 from $v_1$. $$ H_1 = \{v_i\ |\ d(v_1, v_i) = 1\}\\ H_2 = \{v_i\ |\ d(v_1, v_i) = 2\} $$
Note that $H_1 \cup H_2 = V-\{v_1\}$ since $s_G(v_1) = 2$
If $v_{n+1} \in H_2$, we are done, since we'll still have $s_G(v_1) = 2$.
So we can now assume that $v_{n+1} \not\in H_2$
Note that for any vertices $v_i \in H_2$, we have $(v_i, v_1) \in E$, because otherwise $d(v_1, v_i) = 1$. Also note that $$v_i \in H_2 \Rightarrow \exists v_j \in H_1, (v_j, v_i)\in E \qquad \ldots\ (1)$$ (i.e., if player $i$ is of distance 2 from player $1$, there exists another player that is beaten by player $1$ and that player beats player $i$).
Since $v_{n+1} \not\in H_2$, it means $$\forall v_j\in H_1, (v_{n+1}, v_j)\in E \qquad \ldots (2)$$ (i.e., everyone that was beaten by player $1$ is also beaten by player $n+1$).
By $(1)$ and $(2)$, we have $$\forall v_i \in H_2, d(v_{n+1}, v_i) \leq 2$$ (i.e., everyone with distance 2 from player $1$ is at most of distance 2 from player $n+1$)
This means we have $$\forall v_i \in H_1, d(v_{n+1}, v_i) = 1\\\forall v_i \in H_2, d(v_{n+1}, v_i) \leq 2$$ which means that $s_G(v_{n+1}) \leq 2$ (since $H_1 \cup H_2 = V-\{v_1\}$), so the property holds.
We have proven that if the property holds in a graph with $n$ vertices, it also holds in a graph with $n+1$ vertices. By induction, the property is true for all $n$.
Q.E.D.
Constructive proof:
Consider a person P who won the greatest number of matches. (If there is a tie for most, choose any of them.) This person is a dominant player.
If P is not a dominant player, then some person Q beat P and every person P beat. But this is more people than P beat, contradicting the choice of P as the player with the most victories.
I will try to "prove" this with a tournament of 4 people first. This may be followed up with 5 or 6 person solutions, if necessary.
First, let's consider the possible cases. Each person must play 3 games, the amount of wins must equal the amount of losses, and no two players can be undefeated. Likewise, no two players can be 0-3.
A B C D
3-0, 2-1, 1-2, 0-3
3-0, 1-2, 1-2, 1-2
2-1, 2-1, 1-2, 1-2
2-1, 2-1, 2-1, 0-3
Cases 1 and 2 can be disregarded, as someone is undefeated.
In Case 3, I will assume A beat B, even though the proof can be reversed if B beats A. A beat B, so that means either C beat A or D beat A. However, B beat both C and D, so B is one such player in this tournament.
In Case 4, A beat B, B beat C, and C beat A. All three of these beat D. This is already solved, as A, B, and C all fit the requirements.
A B C D E
3-1, 3-1, 2-2, 1-3, 1-3
3-1, 2-2, 2-2, 2-2, 1-3
2-2, 2-2, 2-2, 2-2, 2-2
These are the only cases I need to prove. All other ones include either an undefeated team or a team with no wins, so these are identical to a 4 team tournament. The last team is either unimportant or it is the team that fulfills the requirements.
Case 1 - A beats B, which means A loses to C, D, or E. B beat all three of these teams, so B is one solution.
Case 2 - Either E beat A or B beat A. The other situations are variants of this. If E beat A, then A is the correct team, because A beat B, C, and D, all of which beat E. If B beat A, then A is again the correct team, because A beat C, D, and E, and B lost to exactly two of these teams.
Case 3 - This is Rock Paper Scissors Lizard Spock. Every choice actually fits the requirements.
I am going to prove this using mathematical induction.
Let there be an arrow from A to B if A has defeated B.
When there are exactly 2 players then the person who has defeated the other player is the dominant player.
Now, we need to prove that there being a dominant player among n players implies that there will be a dominant player among n+1 players as well. Here is the proof :
Let x be the dominant player among n players. Let s be the subset of players that x has defeated himself. Now, let us introduce the (n+1)th player. There are 3 possibilities :
The (n+1)th player has been defeated by x. This means that we still have found a dominant player among n+1 players namely x.
x has been defeated by the (n+1)th player but there is some player in the subset s who has defeated this (n+1)th player. This means that we still have a dominant player namely x.
x and all the players in s have been defeated by the (n+1)th player . Even in this case, we will still have a dominant player. This time, he is the (n+1)th player.
Thus, we see that if it is true for n then it will also be true for n+1 .
