Knock-out
Problem
A table-tennis championship for $2^n$ players has $n$ rounds and is organized as a knock-out tournament, with players randomly matched together at the start. The last round is the final.
Before the tournament starts, I decide to pick two players to support at random from the list of entrants. What is the probability that they have to play against each other at some point in the tournament?
You may also be interested to try the more challenging problem FA Cup.
Getting Started
What is the probability of the players meeting in the first round?
What is the probability of both players getting into the second round?
What is the probability of the players meeting in the second round?
Student Solutions
This solution was sent in by Paul from Berkhamsted Collegiate School.
To solve this problem we can, without loss of generality, think of the first player as being at the top of the draw. We MUST also assume that the chances of winning any given match is $1/2$. Then the chance of the players meeting in the first round (with $2^n$ participants) is $p=1/(2^{n} - 1)$.
The chances of the two players not meeting in the first round and winning their first round matches is:
For $2^n$ paricipants there will be $n$ rounds, so we can sum ALL the probabilities of meeting in a certain round, and we get