Knock-out
Before a knockout tournament with 2^n players I pick two players. What is the probability that they have to play against each other at some point in the tournament?
Age
16 to 18
Challenge level
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.
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?
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: $$(1 - {1\over 2^{n} - 1})\times {1\over 4} = {2^{n-1}-1\over 2(2^n - 1)}.$$ It follows that the chance of the two players being drawn to meet in the second round is: $$ {2^{n-1}-1\over 2(2^n - 1)}\times {1\over(2^{n-1} - 1)} = {1\over 2(2^n-1)}= {p\over 2}.$$ So the odds of them meeting in the second round is half those of meeting in the first round. By the same reasoning the probability of meeting in each subsequent round is half the probability of meeting in the previous round.
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 $$ \eqalign{ {1\over 2^n - 1} \left({1\over 1} + {1\over 2} + {1\over 4} + \cdots {1\over 2^{n-1}}\right) &= {1\over 2^n - 1} \left(2- {1\over 2^{n-1}}\right) \\ &= {1\over 2^n - 1}\left( {2^n - 1\over 2^{n-1}}\right) \\ &= {1\over 2^{n-1}}.}$$ So the probability of the two players meeting if there are $2^n$ players competing is ${1\over 2^{n-1}}$.