5
$\begingroup$

I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given competition between two players is known, but the order of competitions is not. Suppose that I have some tournament of the form $p_1, p_2, p_3, ..., p_n$ and I know that $p_1$ may win the entire tournament (depending on the order of competitions). Can I show that $p_1$ must beat some possible winner of a tournament on just $p_2, p_3, ..., p_n$?

I originally came to this while proving the correctness of an algorithm to determine the list of possible winners of a general tournament, but this specific subproblem is giving me trouble.

To begin an attempt at a solution, I offer that in the contrary case, $p_1$ must only compete against and beat some sequence of "losers" (players who cannot win the tournament on just $p_2, ..., p_n$ no matter the order played), with no winners losing to $p_1$. This implies that at some point, a loser must defeat a winner. This may be impossible? I can't prove that, and I don't know whether that's even true.

$\endgroup$
  • $\begingroup$ In case it's helpful, Yuval's nice proof also works for the case where any pair of players (not just an adjacent pair) can compete, with only the minor changes that in the second branch of the proof, $p_2$ becomes an arbitrary $p_j$ with $j \notin \{1, i\}$, and $p_3, \dots, p_n$ becomes $\{p_2, \dots, p_n\} \setminus \{p_j\}$. $\endgroup$ – j_random_hacker Feb 12 at 14:29
4
$\begingroup$

Here is a proof by induction. The base case, $n = 2$, is clear.

Now consider a tournament in which $p_1$ wins. Suppose first that the first competition doesn't involve $p_1$. Let the new set of players be $p_1,P$. By induction, we know that $p_1$ must beat one of the possible winners of the tournament in $P$, say $p_i$. Since the first competition didn't involve $p_1$, $p_i$ can also win the tournament on $p_2,\ldots,p_n$, completing the proof in this case.

Suppose next that the first competition has $p_1$ beating $p_2$. Applying the induction hypothesis, we know that $p_1$ must beat one of the possible winners of the tournament in $p_3,\ldots,p_n$, say $p_i$. If $p_i$ beats $p_2$, then $p_i$ can also win the tournament on $p_2,\ldots,p_n$, and we're done. If $p_2$ beat $p_i$, then $p_2$ can win the tournament on $p_2,\ldots,p_n$, and so we're again done (since in the first competition, $p_1$ beat $p_2$).

$\endgroup$
2
$\begingroup$

We are talking about single-elimination tournament throughout.

Here is a proof to confirm a positive answer to the question.

Let $p_1$ win an entire tournament $T$. For every other player $q$, consider its losing chain $q=l(0), l(1),l(2),\cdots, l(d_T(q))=p_1$, where player $l(i)$ loses to player $l(i+1)$ in $T$ for all $i$, $0\le i\lt d_T(q)$. We call $d_T(q)$ the losing degree of player $q$ in $T$.

Let $w$ be the player among champions of all possible tournaments among players other than $p_1$ such that its losing degree $d_T(w)$ is the smallest, i.e., $w$ is "the closest to win" in $T$. Suppose $w$ loses to $s$ in $T$, i.e., $d_T(s)=d_T(w)-1<d_T(w)$. If $s$ is not $p_1$, then $s$ can be the champion of a possible tournament among players other than $p_1$ as well, which contradicts the minimality of $d_T(w)$. So $s$ must be $p_1$. The proof is done.


To begin an attempt at a solution, I offer that in the contrary case, $p_1$ must only compete against and beat some sequence of "losers" (players who cannot win the tournament on just $p_2,\cdots,p_n$ no matter the order played), with no winners losing to $p_1$. This implies that at some point, a loser must defeat a winner. This may be impossible? I can't prove that, and I don't know whether that's even true.

"A loser must defeat a winner" is indeed impossible. To continue your approach, you need to find and take advantage of the extreme case as shown in the above proof. That is, among all cases of "a loser defeat a winner", select the winner that is closest to win the entire tournament.


Here are several related easy exercises.

Exercise 1. (One minute or less) Show that $s$ can be a possible winner of a tournament among $p_2, p_3,\cdots, p_n$ indeed in the above proof.

Exercise 2. For each player $p$, let $d(p)$ be the smallest $d_T(p)$ among all possible tournament $T$ on all players. Call $d(p)$ the losing degree of $p$. Show that $d(p)\ge d(q)$ if $p$ plays worse than $q$. Give an example when the equality does hold.

Exercise 3. Generalize the above to tournaments among the vertices of a general directed graph $G$ that has no parallel edges, whose edge $(v_i,v_j)$ means vertex $v_i$ plays worse than vertex $v_j$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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