4
$\begingroup$

A chess tournament (single-elimination format) has 16 players. Suppose that no two players have the same strength, and that each player always defeats the players weaker than himself/herself (i.e. no draws). The loser of the final round becomes the runner-up. What is the chance that the second-best player turns out to be the runner-up? What if there are $2^n$ players?

I'm not sure how to approach this. Would it be correct to think that the the probability is $\frac{14}{15} \times \frac{6}{7} \times \frac{2}{3}$, since at each round, there is only one person who can cause the player not to advance, and the number of players in each round is halved?

How then, would I approach the follow-up question, where I am supposed to answer this in the general case?

$\endgroup$
  • 3
    $\begingroup$ Looks good to me. Observe that the product simplifies to $8/15$. $\endgroup$ – Jyrki Lahtonen Sep 22 '14 at 7:38
6
$\begingroup$

The second best player will always lose when they play the best player. They will come second if they reach the final. They will reach the final if they don't meet the best player prior. Therefore they will come second if they are in the opposite half of the draw to the best player.

If they are seeded then $p=1$.

If they are assigned randomly then $p=\frac{8}{15}$, or for the general case of $2n$, $p=\frac{n}{2n-1}$

$\endgroup$
  • 1
    $\begingroup$ I understand your answer, but I'm having trouble understanding why my reasoning for the probability is incorrect... Isn't it true that for the round of $n$ players, the probability of the second-best player advancing $\frac{n-2}{n-1}$? And by multiplying this probability for successive rounds, I was under the impression that it would give me an answer... $\endgroup$ – calvin cheng Sep 22 '14 at 7:16
  • 4
    $\begingroup$ Hmm. In a field of sixteen players wouldn't the probability of the best player to be on the other side of the bracket be $8/15$ as opposed to $1/2$? You place the second best player in some random slot. Then there will be 7 open slots on the same half and 8 on the opposite half for the best player to be put on. Thus $8/15$ ways of placing the best work out well for our runner-up. BTW, this is what the OP's calculation simplifies to. Generalization to $2^n$ players is immediate. $\endgroup$ – Jyrki Lahtonen Sep 22 '14 at 7:33
  • 3
    $\begingroup$ Please note that $p = 0.5$ is wrong for the second case. If the strongest player is on one side of the draw, the probability for the second best to be on the other side is $8/15 = 0.5333...$ because one possibility has been taken by the best player. Hence, OP's calculation is correct (but overly complex, I agree). $\endgroup$ – Traklon Sep 22 '14 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.