It's a KnockOut

8 players: p 1 , p 2 , p 3 , p 4 , p 5 , p 6 , p 7 p_1,p_2,p_3,p_4,p_5,p_6,p_7 and p 8 p_8 play a knock out tournament. It is known that if players p i p_i and p j p_j play, p i p_i always wins if i < j i<j . Suppose that players are paired at random in each round, find the probability that player p 4 p_4 reaches the final.

Give your answer to 3 decimal places.

Also try : How could it be so Probable


The answer is 0.1142.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Avraam Aneleitos
Aug 30, 2015

In order to reach the final p 4 p_4 needs to face two of p 5 , p 6 , p 7 p_5,p_6,p_7 and p 8 p_8 in the first two rounds. His chance of facing one of them in the first round is 4 7 \frac{4}{7} .

Next, his chance of facing one more in the second round depends on the other matches of the first round. If each one of p 1 , p 2 p_1,p_2 and p 3 p_3 faces one of p 5 , p 6 p_5,p_6 and p 7 p_7 (supposing p 4 p_4 faced p 8 p_8 in the first round without loss of generality) then he can't reach the final. So two of p 5 , p 6 p_5,p_6 and p 7 p_7 must have faced each other in the first round and the chance of this happenning is 9 15 = 3 5 \frac{9}{15}=\frac{3}{5} .

Finally once p 4 p_4 and one of p 5 , p 6 p_5,p_6 and p 7 p_7 are on the second round the chance of them facing each other is 1 3 \frac{1}{3} .

Thus the chance of p 4 p_4 reaching the final is 4 7 3 5 1 3 = 4 35 = 0.114 \frac{4}{7}\cdot\frac{3}{5}\cdot\frac{1}{3}=\frac{4}{35}=0.114

Well done. Nice

Mayank Singh - 5 years, 9 months ago

Log in to reply

You see, this is the part where our friend @Prakhar Jain just went a little wrong. :D

Sanchit Aggarwal - 5 years, 9 months ago

Log in to reply

yeah got it wrong during the second round instead of thinking that p5,p6 and p7 can be matched up in 2 cases i fixed p5 as taking on either of them hence getting the chances down to 2/5

Prakhar Jain - 5 years, 9 months ago
Theodore Anthiros
Aug 31, 2015

We can divide the tournament into two 4-man "conferences". p 4 p_4 will win his conference and reach the final if and only if the three better players are all in the other conference. We can place them in order. For p 1 p_1 , there are three spots in p 4 p_4 's conference and four in the other, so he has a 4 7 \frac{4}{7} chance of being in the other. This takes up one spot, so p 2 p_2 has a 3 6 \frac{3}{6} chance. This leaves 2 5 \frac{2}{5} for p 3 p_3 . Multiplying all of these together gives 4 35 \frac{4}{35} .

Mayank Singh
Aug 30, 2015

Lets first find the total number of cases.

Apply the simple concept of distribution to divide the players in sets of two for round 1. This would give 8 ! 2 ! 4 . 4 ! \frac{8!}{2!^4.4!} number of ways for round one. Now for round 2, we would be having a total of 4 players left, again distributing them into 2 sets of two players 4 ! 2 ! 2 . 2 ! \frac{4!}{2!^2.2!} . So total number of cases are 8 ! 2 ! 4 . 4 ! . 4 ! 2 ! 2 . 2 ! \boxed {\frac{8!}{2!^4.4!}.\frac{4!}{2!^2.2!}}

Now for the favourable cases. p4 must play match with either of p5,p6,p7 or p8. Now we have 3 players less than p4 and 3 players more than p4 in subscript. It can't be that the lesser players would play with higher players as then p4 won't win the semi final, hence 2 of the higher players must play a match among them. So we have to "select one from the 4 higher players to match against p4" * "select any 2 from the remaining 3 players to match among them"*"Distribute the 3 lower players and 1 higher player". In the semis, we have only one way with which p4 can reach the finals(i.e. it must play with the higher player remaining). Framing the above line Mathematically, we get 4 C 1 . 3 C 2 . 4 ! 2 ! 2 . 2 ! . 1 \boxed{4C_{1}.3C_{2}.\frac{4!}{2!^2.2!}.1}

Divide them for the probability

Ashish Gupta
Feb 12, 2017

The number of ways in which p 1 , p 2 , . . . , p 8 p_1, p_2, ..., p_8 can be paired is
= 1 4 ! ( 8 2 ) ( 6 2 ) ( 4 2 ) ( 2 2 ) \frac{1}{4!} {8 \choose 2} {6 \choose 2} {4 \choose 2} {2 \choose 2}
= 105 ways

Now, at least two players certainly reach the second round in between p 1 , p 2 , p_1, p_2, and p 3 p_3 .

p 4 p_4 can reach in final if in the first round, this happens \rightarrow

  • Exactly two players play against each other in between p 1 , p 2 , p 3 p_1, p_2, p_3
  • the remaining player plays against one of the players from p 5 , p 6 , p 7 , p 8 p_5, p_6, p_7, p_8 .
  • p 4 p_4 plays against one of the remaining three from p 5 , p 6 , p 7 , p 8 . p_5, p_6, p_7, p_8.

This can be possible in
= ( 3 2 ) ( 4 1 ) ( 3 1 ) {3 \choose 2} {4 \choose 1} {3 \choose 1}
= 36 ways

\Rightarrow Probability that p 4 p_4 and exactly one of p 5 , . . . p 8 p_5, ... p_8 reach second round is
= 36 105 \frac{36}{105} = 12 35 \frac{12}{35}

If p 1 , p i , p 4 p_1, p_i, p_4 and p j p_j where i i = 2 or 3 and j j = 5 or 6 or 7 reach the second round, then they can be paired in
= 1 2 ! ( 4 2 ) ( 2 2 ) \frac{1}{2!} {4 \choose 2}{2 \choose 2} = 3 ways

But p 4 p_4 will reach the final if p 1 p_1 plays against p i p_i and p 4 p_4 plays against p j p_j .
Hence, the probability that p 4 p_4 reaches the final round from the second round is 1 3 \frac{1}{3} .

Therefore, probability that p 4 p_4 reaches the final round is 12 35 × 1 3 \frac{12}{35} \times \frac{1}{3} = 4 35 \frac{4}{35}

Alan Yan
Sep 3, 2015

Let us set this up like a tourney. It is a row of 8 people and places 1, 2 ; 3, 4 ; 5, 6 ; 7, 8 face each other. If you split it into two groups by the half, you know in the half of p 4 p_4 , there can only be p 5 , p 6 , p 7 , p_5, p_6, p_7, and p 8 p_8 .

Therefore the numerator is : 8 4 3 2 4 ! 8 \cdot 4 \cdot 3 \cdot 2 \cdot 4!

because there are 8 ways to put the p 4 p_4 , 4 3 2 4\cdot 3 \cdot 2 ways to put down p 5 , p 6 , p 7 , p 8 p_5 , p_6, p_7, p_8 and 4 ! 4! to be the rest.

Therefore the probability is 8 4 3 2 4 ! 8 ! 0.114 \frac{8 \cdot 4 \cdot 3 \cdot 2 \cdot 4!}{8!} \approx 0.114

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...