Every tournament has a dominant player

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.

4 Teams

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.

5 Teams

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.

Proof by induction

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 }itext{ 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) | vin 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:

1. $(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.

2. $(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} notin 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} notin H_2$, it means $$forall v_jin 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) = 1forall 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.

---

For the interest of those who don't speak math, here is a slightly less formal explanation (which I just realized is much much easier to understand than mumbo jumbo above =p):

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. =)

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.