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

  • 1
    $\begingroup$ 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? $\endgroup$ – Ross Millikan Sep 30 '19 at 3:24
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.