Problem 4.18 Easy Free 2 variations

Top Two Seeds Meet in the Final

A knockout chess tournament has $128$ players with distinct ratings, drawn into a uniformly random bracket of $7$ rounds. In every match the higher-rated player always wins and advances. Find the probability that the two highest-rated players meet in the final.

Work it out, then compare with the answer.

SolutionShow the worked solution

Since nobody can beat the top seed $P_1$ , $P_1$ wins every match and always reaches the final. The final is played between the winners of the two halves of the bracket, each of $64$ slots.

If the second seed $P_2$ is in the other half from $P_1$ , then $P_2$ is the strongest player in that half. So $P_2$ wins that half and meets $P_1$ in the final.
If $P_2$ is in the same half as $P_1$ , the two must meet before the final, and $P_2$ is knocked out.

The bracket is uniformly random. So, given $P_1$ ’s slot, $P_2$ is equally likely to occupy any of the other $127$ slots. Exactly $64$ of these lie in the opposite half. Hence

\boxed{\mathbb{P}(\text{$P_1$ and $P_2$ meet in the final})=\frac{64}{127}\approx 0.504}

Key idea. The top seed always reaches the final, so only the second seed’s half of the bracket matters.

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 4.18a

Work it out, then compare with the answer.

Solution

As before, $P_1$ always reaches the final. The third seed $P_3$ reaches the final exactly when two things hold:

$P_3$ is in the other half from $P_1$ , where it must then be the strongest player;
$P_2$ is not in $P_3$ ’s half, so $P_2$ must be in $P_1$ ’s half.

Given $P_1$ ’s slot, $P_2$ lands in $P_1$ ’s half with probability $\frac{63}{127}$ . Given that, $P_3$ lands in the other half with probability $\frac{64}{126}$ . Therefore

\mathbb{P}=\frac{63}{127}\cdot\frac{64}{126}=\boxed{\frac{32}{127}\approx 0.252}

Variation 4.18b

A knockout chess tournament has $2^n$ players with distinct ratings, drawn into a uniformly random bracket of $n$ rounds. In each match the higher-rated player wins with probability $p$ , where $0.5 < p < 1$ , and advances. Express, as a function of $n$ and $p$ , the probability that the second-highest-rated player beats the highest-rated player in the final. Evaluate this function at $n=4$ , $p=\frac{3}{4}$ .

Work it out, then compare with the answer.

Solution

For $P_1$ and $P_2$ to meet in the final, they must start in opposite halves. This happens with probability $\frac{2^{n-1}}{2^n-1}$ .

Given this, $P_1$ is the higher-rated player in each of its $n-1$ matches within its half, so it wins all of them with probability $p^{n-1}$ .

$P_1$ is absent from $P_2$ ’s half, so $P_2$ is likewise the higher-rated player in each of its $n-1$ matches. It wins them all with probability $p^{n-1}$ , independently of $P_1$ ’s results.

In the final, $P_2$ beats $P_1$ with probability $1-p$ . Hence

\mathbb{P}=\frac{2^{n-1}\,p^{2n-2}\,(1-p)}{2^n-1}.

At $n=4$ and $p=\frac34$ :

\frac{8}{15}\left(\frac34\right)^{6}\cdot\frac14=\frac{2}{15}\cdot\frac{729}{4096} =\boxed{\frac{243}{10240}\approx 0.0237}

Spotted an error? Email us