HMMT 二月 2021 · 冲刺赛 · 第 13 题

HMMT February 2021 — Guts Round — Problem 13

[11] 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 b 2021 p c . √

解析

[11] 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 b 2021 p c . Proposed by: Milan Haiman Answer: 674 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 1 the best team with probability , so the second-best team survives the round with probability k ( ) 2 2 1 2 k − k − 2 ( k + 1)( k − 2) 1 − ( ) = 1 − = = . k k ( k − 1) k ( k − 1) k ( k − 1) 2 So, the probability that the second-best team survives every round before the last round is 2021 ∏ ( k + 1)( k − 2) , k ( k − 1) k =3 which telescopes to 2022! 2019! · 2022! · 2019! 2! · 1! 2022 1 337 3! 0! = · = · = = p. 2021! 2020! 2021! · 2020! 3! · 0! 2020 3 1010 · 2! 1! So, ⌊ ⌋ ⌊ ⌋ 2021 · 337 1 b 2021 p c = = 337 · 2 + 337 · = 337 · 2 = 674 . 1010 1010 √