Home > Riddles > The row ganadora

The row ganadora

Master playsLevel 3/5

In a tournament without ties, the entire result can seem chaotic. But there is always a way to order the players so that each one has beaten the next.

Eight chess players play a free-for-all tournament. Each pair faces off once and no game ends in a draw.

Someone claims that, no matter what happens in the tournament, it will always be possible to arrange the eight players in a row so that each player has beaten the one immediately behind him. Is he right, or can a tournament be built where that line is impossible?

Hints

Show hints
  1. Try building the row little by little.
  2. If you already have a valid row for k players, try inserting the new player in the appropriate place.
  3. Go down the line until you find the first player the new player has beaten.

Solution

Show full solution

Answer: you are right. That line always exists. We are going to build it by incorporating the eight players one by one. With only one player, the line already meets the condition: there is no one behind him. Now suppose we have already got a valid row with $k$ players, where $1\le k<8$: $$
P_1\to P_2\to\cdots\to P_k,

$$ and the arrow means “won.” We want to add a new player $X$. If $X$ beat $P_1$, we put it at the beginning: $$

X\to P_1\to P_2\to\cdots\to P_k.

$$ If $P_k$ beat $X$, we put it last: $$

P_1\to P_2\to\cdots\to P_k\to X.

$$ The case remains in which it cannot go to the beginning or the end. So $P_1$ beat $X$, but $X$ beat $P_k$. We go down the row from the beginning and look for the first player that $X$ has beaten. That player exists, because $X$ beat $P_k$. Call it $P_{i+1}$. Since he is the first one $X$ beat, the previous player, $P_i$, had to beat $X$. So we have: $$

P_i\to X

$$ and $$

X\to P_{i+1}.

$$ We insert $X$ between them: $$

P_1\to\cdots\to P_i\to X\to P_{i+1}\to\cdots\to P_k.
$$ The row is still valid, because we have only replaced the $P_i\to P_{i+1}$ link with two valid links: $P_i\to X\to P_{i+1}$. This procedure allows you to go from a valid row of $k$ players to a valid row of $k+1$ players. We start with 1 player and repeat the process until we reach 8. Thus we obtain a valid row with the eight chess players. Furthermore, the reasoning does not use anything special about the number 8: it works the same for any number of players. In every tournament without ties there is a row in which each player has beaten the next.

Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The envious dice · Next: The tournament of ties →