patternMinor
Must the champion of an entire tournament beat the champion of a possible tournament among other players?
Viewed 0 times
amongthetournamentmustentirebeatplayerschampionpossibleother
Problem
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.
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.
Solution
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$).
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$).
Context
StackExchange Computer Science Q#104225, answer score: 4
Revisions (0)
No revisions yet.