Maths Olympiad Prep

Library / /16 of 19

, 2021

Algebra Difficulty 5.6 AIME, harder Prove it United States

Problem:
A tournament among 20212021 ranked teams is played over 20202020 rounds. In each round, two teams are selected uniformly at random among all remaining teams to play against each other. The better ranked team always wins, and the worse ranked team is eliminated. Let pp be the probability that the second best ranked team is eliminated in the last round. Compute 2021p\lfloor 2021 p \rfloor.

Solution

Solution:
In any given round, the second-best team is only eliminated if it plays against the best team. If there are kk teams left and the second-best team has not been eliminated, the second-best team plays the best team with probability 1(k2)\frac{1}{\binom{k}{2}}, so the second-best team survives the round with probability
11(k2)=12k(k1)=k2k2k(k1)=(k+1)(k2)k(k1). 1 - \frac{1}{\binom{k}{2}} = 1 - \frac{2}{k(k-1)} = \frac{k^2 - k - 2}{k(k-1)} = \frac{(k+1)(k-2)}{k(k-1)}.
So, the probability that the second-best team survives every round before the last round is
k=32021(k+1)(k2)k(k1) \prod_{k=3}^{2021} \frac{(k+1)(k-2)}{k(k-1)}
which telescopes to
2022!3!2019!0!2021!2!2020!1!=2022!2019!2021!2020!2!1!3!0!=2022202013=3371010=p \frac{\frac{2022!}{3!} \cdot \frac{2019!}{0!}}{\frac{2021!}{2!} \cdot \frac{2020!}{1!}} = \frac{2022! \cdot 2019!}{2021! \cdot 2020!} \cdot \frac{2! \cdot 1!}{3! \cdot 0!} = \frac{2022}{2020} \cdot \frac{1}{3} = \frac{337}{1010} = p
So,
2021p=20213371010=3372+33711010=3372=674 \lfloor 2021 p \rfloor = \left\lfloor \frac{2021 \cdot 337}{1010} \right\rfloor = \left\lfloor 337 \cdot 2 + 337 \cdot \frac{1}{1010} \right\rfloor = 337 \cdot 2 = 674

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.