HMMT-Feb 2021 guts, Problem 13

A tournament among 2021 ranked teams is played over 2020 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 $p$ be the probability that the second best ranked team is eliminated in the last round. Compute $\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 $k$ teams left and the second-best team has not been eliminated, the second-best team plays the best team with probability $\frac{1}{\left(\begin{array}{c}k \\ 2\end{array}\right)}$, so the second-best team survives the round with probability \[ 1-\frac{1}{\left(\begin{array}{c} k \\ 2 \end{array}\right)}=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 \[ \prod_{k=3}^{2021} \frac{(k+1)(k-2)}{k(k-1)} \] which telescopes to \[ \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, \[ \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 \] $\fbox{674}$.

Answer: 674