Eight players P1, P2, …… P8 play a knock-out tournament. It is known that whenever the players Pi and Pj play, the play Pi will win if i < j. Assuming that the players are paired at random in each round, what is the probability that the player P4 reaches the final?

420 Points
13 years ago

Dear Lav

This is very important problem to understand concept of prbability. So i am putting detailed solution.

P1 and P8 have their fate established no matter the arrangement.
P1 will win every match and the entire tournament, and P8 will lose in the first round.
For the other players, it depends who they play and when.

A player advances to the second round if he plays a higher numbered player
in the first round, and advances to the final if that happens again.

Each players chance of success in round 1 is:
P1: 7/7 (opponent doesn't matter)
P2: 6/7 (any opponent except P1)
P3: 5/7 (4, 5, 6, 7, or 8)
P4: 4/7 (5, 6, 7, or 8)
P5: 3/7 (6, 7, or 8)
P6: 2/7 (7 or 8)
P7: 1/7 (8)
P8: 0/7 (loses to all)

For the chance of a second-round win, we examine each tournament format separately.

A) Pre-set brackets

To reach the finals, a player must be the lowest numbered player in his half of the bracket.
Let's call the places on the bracket "slots".
And we'll say the following slots play in the first round:
A-B, C-D, E-F, G-H.
Then winner of A-B plays winner of C-D,
and winner of E-F plays winner of G-H.
The final is then between the winners of those two,
but we don't care about that, because P1 will always be there and win.

We can start by assigning each player in turn to slot A,
and evaluate the possibilities. By symmetry, the same result
would be also be obtained with the player in any other slot,
so we would just be doing redundant work to figure it that way.

P2: will win second round match if P1 is in the other half, so his chances are 4/7
P3: will win second round match if P1 and P2 are in the other half. P1 will be over there 4/7 of the time, and of those, P2 will be over there 1/2 the time. 2/7 chance.
P4: Needs P1, P2, P3 in other half: 4/7 × 3/6 × 2/5 = 4/35 chance.
P5: Needs P1-P4 in other half: 4/7 × 3/6 × 2/5 × 1/4 = 1/35 chance.

Since there are two slots in the final, we have a 200% total chance for players reaching the final:
1.0 for P1 and 4/7 + 2/7 + 4/35 + 1/35 = 1.0 for P2-P5.

The remaining players have no chance of reaching the final at all,
since there are not enough slots in the other half of the bracket.

B) Random pairings on every round.

P1: sure winner no matter what

P2: 6/7 chance of not playing P1 in the first round × 2/3 chance in second round: 4/7 chance

P3: 5/7 chance of winning first round
In second round:
if P1 played P2 in first round (1/5 chance), then 2/3 chance.
If P1 didn't play P2 in first round (4/5 chance), then 1/3 chance.
Total chance: 5/7 × (1/5 × 2/3 + 4/5 × 1/3) = 5/7 × (2/15 + 4/15) = 5/7 × 6/15 = 2/7

P4: 4/7 chance of winning first round.
Among P1, P2, P3 there could be 0 or 1 first round matches.
Chances of 0 matches:
P4 is playing one of P5,P6,P7,P8,
leaves the other three to play P1, P2, P3, so 3/5 × 2/3 × 1/1 = 2/5 chance of that.
Then P4 has no chance, since P1, P2, P3 will all be in second round.

Chances of 1 match: 3/5
Then P4 has 1/3 chance of not facing P1, P2, or P3 in second round.
4/7 × ( 3/5 × 1/3 ) = 4/7 × 1/5 = 4/35

P5: 3/7 chance in first round.
Second round opponent must be P6, P7, P8.
He played one of them in first round, then the other two
must have played each other: 1/5 chance.
Then 1/3 chance P5 will play the survivor: 1/15 overall.
3/7 * 1/15 = 1/35

P6, P7, P8: no chances

Put P4 in slot A.
Then Slots B-C-D must be chosen from players 5,6,7,8.
And it doesn't matter in which order.

There are P(7,3) ways to put ANY players in those slots,
and P(4,3) ways for them to be among 5,6,7,8.

So probability is P(4,3) / P(7,3)
= 4 x 3 x 2 / (7 x 6 x 5) = 24 / 210 = 8/70 = 4/35

All the best.

AKASH GOYAL

Please feel free to post as many doubts on our discussion forum as you can. We are all IITians and here to help you in your IIT JEE preparation.

Win exciting gifts by answering the questions on Discussion Forum. So help discuss any query on askiitians forum and become an Elite Expert League askiitian.