# Tennis tournament proof that $n + 1$ players can form a line

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

• To form a line, we need to find a group of $n+1$ players, one of whom has defeated all the rest. That one can stand in front. There must be a second who defeated all the others except the first, who will stand second, and so on. Try it with small $n$. If $n=1$, there are $2$ players and you need to find $2$ of them who can stand in line. Can you? If $n=2$ there are $4$ players and you need to find $3$. Can you guarantee that? – Ross Millikan Sep 30 '19 at 3:24
• Just in case there's a cultural gap: "A line" of people in some parts of the world is more commonly called "a queue" of people. – Brian Moehring Sep 30 '19 at 3:29

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.