At a tennis tournament, there were $2^n$ participants, and any two of them played against each other exactly one time. Prove that we can find $n+1$ players that can form a line in which everybody has defeated all the players who are behind him in the line.
How would you prove this by induction? Also what does it mean to form a line? Thanks
On average, everyone wins against $(2^n-1)/2$ players, so some player, $x$, has won against $2^{n-1}$ players. Find a line of $n$ among the players $x$ beat (by induction), then put $x$ at the end of the line.