Must the champion of an entire tournament beat the champion of a possible tournament among other players?

cs.stackexchange https://cs.stackexchange.com/questions/104225

  •  05-11-2019
  •  | 
  •  

Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top