Problem 65

Problem 65: A knock-out tournament ( $✓$ ) 1987 Specimen Paper II

A tennis tournament is arranged for $2^{n}$ players. It is organised as a knockout tournament, so that only the winners in any given round proceed to the next round. Opponents in each round except the ﬁnal are drawn at random, and in any match either player has a probability $\frac{1}{2}$ of winning. Two players are chosen at random before the start of the ﬁrst round. Find the probabilities that they play each other:

(i): in the ﬁrst round;
(ii): in the ﬁnal round;
(iii): in the tournament.

Comments

Note that the set-up is not the usual one for a tennis tournament, where the only random element is in the ﬁrst round line-up. Two players cannot then meet in the ﬁnal if they are in the same half of the draw.

Part (i) is straightforward, but parts (ii) and (iii) need a bit of thought. There is a short way and a long way of tackling these parts, and both have merits.

It is a good plan to check your answers, if possible, by reference to simple special cases where you can see what the answers should be; $n = 1$ or $n = 2$ , for example.

Interestingly, the answers are independent of the probability that the players have of winning a match; the $2$ s in the answers represent the number of players in each match rather than (the reciprocal of) the probability that each player has of winning a match. It also does not matter how the draw for each round is made. This is clear if you use the short method mentioned above.

Solution to problem 65

Call the two players $P_{1}$ and $P_{2}$ .

(i) Once $P_{1}$ has been given a slot, there are $2^{n} - 1$ slots for $P_{2}$ , in only one of which will he or she play $P_{1}$ . The probability of $P_{1}$ playing $P_{2}$ is therefore

\frac{1}{2^{n} - 1} .

Note that this works for $n = 1$ and $n = 2$ .

(ii) Long way. To meet in the ﬁnal, $P_{1}$ and $P_{2}$ must each win every round before the ﬁnal, and must also not meet before the ﬁnal. The probability that $P_{1}$ and $P_{2}$ do not meet in the ﬁrst round and that they both win their ﬁrst round matches, is

(1 - \frac{1}{2^{n} - 1}) \frac{1}{2^{2}} i.e. \frac{1}{2} (\frac{2^{n - 1} - 1}{2^{n} - 1}) .

The probability that they win each round and do not meet before the ﬁnal (i.e. for $n - 1$ rounds) is

\frac{1}{2} (\frac{2^{n - 1} - 1}{2^{n} - 1}) \times \frac{1}{2} (\frac{2^{n - 2} - 1}{2^{n - 1} - 1}) \times \dots \times \frac{1}{2} (\frac{2^{1} - 1}{2^{2} - 1}) i.e. \frac{1}{2^{n - 1}} \frac{1}{2^{n} - 1} .

(ii) Short way. Since all processes are random here, the probability that any one pair contests the ﬁnal is the same as that for any other pair. There are a total of $\frac{1}{2} \times 2^{n} (2^{n} - 1)$ different pairs, so the probability for any given pair is $1 ∕ [2^{n - 1} (2^{n} - 1)]$ .

(iii) Long way. We need to add the probabilities that $P_{1}$ and $P_{2}$ meet in each round. The probability that they meet in the $k$ th round is the probability that they reach the $k$ th round times the probability that they meet in the $k$ th round given that they reach it, the latter (conditional) probability being $1 ∕ (2^{n - k + 1} - 1)$ , as can be inferred from part (i). As in part (ii), the probability that they reach the $k$ th round is

\frac{1}{2^{k - 1}} \frac{2^{n - k + 1} - 1}{2^{n} - 1},

so the probability that they meet in the $k$ th round is

\frac{1}{2^{k - 1}} \frac{2^{n - k + 1} - 1}{2^{n} - 1} \times \frac{1}{2^{n - k + 1} - 1} = \frac{1}{2^{k - 1}} \frac{1}{2^{n} - 1} .

Summing this as a geometric progression from $k = 1$ to $n$ gives $1 ∕ 2^{n - 1}$ .

(iii) Short way. By the same short argument as in part (ii), the probability of a given pair meeting in any given match (not necessarily the ﬁnal) is $1 ∕ [2^{n - 1} (2^{n} - 1)]$ . Since the total number of matches is $2^{n} - 1$ (because one match is needed to knock out each player, and all players except one get knocked out), the probability of a given pair playing is

\frac{2^{n} - 1}{2^{n - 1} (2^{n} - 1)} = \frac{1}{2^{n - 1}} .

Post-mortem

If (like me) you plodded through this question the long way, you might be wondering how you were supposed to think of the short way. Instead of working out what happens to individual players as they progress through the tournament, you think about the space of all possible outcomes (the sample space), and attach a probability to each. That way, you can use the symmetry between all the players to help you.