4
$\begingroup$

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.

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

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow. Quite a bit more formal than mine. I think you win. +1 $\endgroup$ – mdc32 Nov 7 '14 at 3:27
  • $\begingroup$ 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. $\endgroup$ – justhalf Nov 7 '14 at 3:31
  • $\begingroup$ 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 $\endgroup$ – mdc32 Nov 7 '14 at 3:35
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "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" $\endgroup$ – justhalf Nov 7 '14 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.