Open Book Publishers logo Open Access logo
  • button
  • button
  • button
GO TO...
book cover

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

A tennis tournament is arranged for 2n 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 final are drawn at random, and in any match either player has a probability 1 2 of winning. Two players are chosen at random before the start of the first round. Find the probabilities that they play each other:

in the first round;
in the final round;
in the tournament.


Note that the set-up is not the usual one for a tennis tournament, where the only random element is in the first round line-up. Two players cannot then meet in the final 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 2s 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 P1 and P2.

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

1 2n 1.

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

(ii) Long way. To meet in the final, P1 and P2 must each win every round before the final, and must also not meet before the final. The probability that P1 and P2 do not meet in the first round and that they both win their first round matches, is

1 1 2n 1 1 22   i.e.      1 2 2n1 1 2n 1 .

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

1 2 2n1 1 2n 1 × 1 2 2n2 1 2n1 1 × × 1 2 21 1 22 1    i.e.       1 2n1 1 2n 1.

(ii) Short way. Since all processes are random here, the probability that any one pair contests the final is the same as that for any other pair. There are a total of 1 2 × 2n(2n 1) different pairs, so the probability for any given pair is 1[2n1(2n 1)].

(iii) Long way. We need to add the probabilities that P1 and P2 meet in each round. The probability that they meet in the kth round is the probability that they reach the kth round times the probability that they meet in the kth round given that they reach it, the latter (conditional) probability being 1(2nk+1 1), as can be inferred from part (i). As in part (ii), the probability that they reach the kth round is

1 2k1 2nk+1 1 2n 1 ,

so the probability that they meet in the kth round is

1 2k1 2nk+1 1 2n 1 × 1 2nk+1 1 = 1 2k1 1 2n 1.

Summing this as a geometric progression from k = 1 to n gives 12n1.

(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 final) is 1[2n1(2n 1)]. Since the total number of matches is 2n 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

2n 1 2n1(2n 1) = 1 2n1.


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.