0
$\begingroup$

I came across an interesting question in a competition (it is long over by now, but I haven't found a solution yet):

In a chess tournament $2^n$ ($n \in \mathbb{N}$) players play each other round-robin (everybody against everybody). If a game draws it is repeated until one of the player wins. Show that it is possible to pick a sequence of $n+1$ players in which each player won over his predecessors.

Obviously this is true for $n = 1$. But I'm stuck even to show this for any higher number.

  • 0
    Took it upon myself to provide a more informative title.2011-11-12

1 Answers 1

5

There must be some player who lost against half the players. Take that player as the first in the sequence, keep $2^{n-1}$ players that she lost against, and discard the remaining players. Now repeat the same procedure with the $2^{n-1}$ until you're left with only one player. At each stage, you're left with only players who won against all the players you've selected for the sequence so far.