7
$\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$
1

5 Answers 5

5
$\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$
5
$\begingroup$

Proof by induction

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:

  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.

$\endgroup$
5
  • $\begingroup$ Wow. Quite a bit more formal than mine. I think you win. +1 $\endgroup$
    – mdc32
    Nov 7, 2014 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, 2014 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, 2014 at 3:35
  • $\begingroup$ After posting my answer, I realised that my answer is exactly the same as your informal one. Request you to either put the easier solution before the mathematical one or mention at the begining of the answer, that you are giving 2 ways to solve the question, one mathematical and another one which is much easier to understand. $\endgroup$ Oct 29, 2021 at 21:43
  • 1
    $\begingroup$ Done. Thanks for your comment on this very old question and answer! The two solution is the same actually, just one is using graph notation. $\endgroup$
    – justhalf
    Oct 30, 2021 at 5:36
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Simple and correct. 👌 Awesome answer. $\endgroup$ Jun 18, 2023 at 23:58
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
  • 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, 2014 at 3:29
2
$\begingroup$

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 :

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

  2. 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.

  3. 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 .

$\endgroup$
3
  • 1
    $\begingroup$ It looks like you need to show something stronger for (2): that there is a player among the first n players who was defeated by x and who has defeated the (n+1)st player. $\endgroup$
    – xnor
    Oct 30, 2021 at 2:04
  • 1
    $\begingroup$ @xnor , you are right. I just fixed it. Is it okay now ? $\endgroup$ Jun 8, 2023 at 3:33
  • $\begingroup$ Yes, this looks like it works now. $\endgroup$
    – xnor
    Jun 8, 2023 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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