1
$\begingroup$

Thirty-two players ranked 1 to 32 are playing in a knockout tournament. Assume that in every match between any two players, the better-ranked player wins, the probability that ranked 1 and ranked 2 players are winner and runner up respectively, is?

My approach:

enter image description here

But the given answer is 16/31. Could someone please explain where i went wrong?

$\endgroup$
3
  • 1
    $\begingroup$ The lowest ranked player cannot get through the first round, but in your calculation that player could fill one of the blanks after the first round. $\endgroup$
    – Bram28
    Feb 23 at 18:03
  • 1
    $\begingroup$ It's obvious that it should be $\frac{16}{31}$: whatever half of the bracket the rank 1 player is in, the rank 2 player should be in the other half. But, that doesn't explain what went wrong with your approach. See my Comment above and Haris' answer for that, and also see Haris' answer for a nice fix that does follow your approach. $\endgroup$
    – Bram28
    Feb 23 at 18:18
  • $\begingroup$ Please don't use images of text/math on this site. $\endgroup$ Feb 24 at 6:27

2 Answers 2

3
$\begingroup$

There are a couple of mistakes in your approach.

One, you are excluding player 1 (top-ranked) from all five matches - the whole tournament basically. You should be considering only the first four matches.

Two, your approach assumes that every player is equally likely to face the top ranked (or second ranked) player in the four matches building up to the finals. That's not correct. The lower a player's rank, the less likely he/she is to play against either of the two players.

Correct Solution

Here's one approach we could take to solve this problem.

There will be $4$ matches before the final. For players with rank $1$ and $2$ to be the winner and the runner-up, they must both reach the finals. And for that to happen, the only condition necessary is that they don't meet in earlier matches. They are guaranteed to win against other opponents.

Looking at things from the perspective of any of the two players (I'm going with rank 1), the total number of ways in which their opponents to the first four matches can be selected are $31 \times 15 \times 7 \times 3$. In the first round, there are 31 players to choose from, in the second, 15, and so on.

But for the question's condition to be met, we will have to exclude the second-ranked player in each stage. Remember they can't play against each other before the final. So, the number of ways to choose opponents for player 1 would be $30 \times 14 \times 6 \times 2$.

Hence the required probability would be

$$\frac{30 \times 14 \times 6 \times 2}{31 \times 15 \times 7 \times 3} = \frac{16}{31}$$

$\endgroup$
5
  • 2
    $\begingroup$ Nice! Good explanation what is wrong with the OP's calculation ... and a nice fix too! There is of course a much easier way to see that the probability should be $\frac{16}{31}$, since the two players simply need to be on opposite sides of the bracket when split in half, but your approach is still in line with the approach the OP is taking... it effectively fixes where the OP went wrong in the details, thus showing that the OP's way of thinking can still work, instead of offering up the much simpler explanation that follows a completely different approach. Good work! :) $\endgroup$
    – Bram28
    Feb 23 at 18:05
  • $\begingroup$ Thank you for your kind words. The solution you propose would be so much more elegant, besides being simpler. The difference would become much obvious if there were more players, say, 256. Why don't you go ahead and post it as an answer? I think it would be helpful to many who may not read the comments. $\endgroup$
    – Haris
    Feb 23 at 18:37
  • $\begingroup$ OK, will do! Just want to make sure the OP accepts your Answer, rather than mine. I'll add a note :) $\endgroup$
    – Bram28
    Feb 23 at 19:41
  • $\begingroup$ Greatly appreciate it! :) $\endgroup$
    – Haris
    Feb 23 at 20:37
  • $\begingroup$ Thanks! I got my mistake $\endgroup$ Feb 24 at 3:39
3
$\begingroup$

What is wrong with your calculation is that you don't take into account that for any match the lower-ranked player always loses. So that puts constraints on which players can be placed in the 'blank' spots, whereas in your calculation any players could end up in any black spot. As a simple example: the lowest ranked player cannot get through the first round, but in your calculation that player could fill one of the blanks after the first round.

Now, I really like @Haris Answer in which they give the same explanation .. but also provide a nice fix using your approach! So you should definitely accept their Answer!

Still, I like to point out that it can be much more easily established that the probability should be $\frac{16}{31}$: in order for the two players to end up in the final, they need to be in opposite halfs of the bracket. So, wherever the rank $1$ player goes, the rank $2$ player needs to be in one of the $16$ spots of the other half, rather than in one of the $15$ spots of the same half.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .