# Every tournament has a dominant player

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.

• @MooingDuck You're asked to show that there exists such a player in the tournament. It won't be BOB but someone else. – xnor Nov 7 '14 at 1:36
• Right right, sorry. – Mooing Duck Nov 7 '14 at 1:40

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.

## 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 }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:

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} \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.

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

• Wow. Quite a bit more formal than mine. I think you win. +1 – mdc32 Nov 7 '14 at 3:27
• Thanks. You could have completely proved (i.e., the "prove" without the quotes =D) it also, if you generalize the method that you used in your answer. – justhalf Nov 7 '14 at 3:31
• Yeah. Mine is pretty easily expandable, just not a real proof. I don't really know exactly what yours is saying, but it kinda makes sense to me. Guess I haven't learned enough combinatorics (or any) to understand this from a logical standpoint :P – mdc32 Nov 7 '14 at 3:35

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.

• "All other ones include either an undefeated team or a team with no losses, so these are identical to a 4 team tournament." I think you meant "or a team with no wins" – justhalf Nov 7 '14 at 3:29