HMMT 十一月 2024 · 冲刺赛 · 第 35 题
HMMT November 2024 — Guts Round — Problem 35
题目详情
- [20] There are 1024 players, ranked from 1 (most skilled) to 1024 (least skilled), participating in a single elimination tournament. In each of the 10 rounds, the remaining players are paired uniformly at random. In each match, the player with a lower rank always wins, and the loser is eliminated from the tournament. For each positive integer n ∈ [1 , 1024] , let f ( n ) be the expected number of rounds that the participant with rank n participates in. Estimate the minimum positive integer N such that f ( N ) < 2 . ( ⌊ ⌋) | E − A | Submit a positive integer E . If the correct answer is A , you will receive max 0 , 20 − points. 2
解析
- [20] There are 1024 players, ranked from 1 (most skilled) to 1024 (least skilled), participating in a single elimination tournament. In each of the 10 rounds, the remaining players are paired uniformly at random. In each match, the player with a lower rank always wins, and the loser is eliminated from the tournament. For each positive integer n ∈ [1 , 1024], let f ( n ) be the expected number of rounds that the participant with rank n participates in. Estimate the minimum positive integer N such that f ( N ) < 2. j k | E − A | Submit a positive integer E . If the correct answer is A , you will receive max 0 , 20 − points. 2 Proposed by: Aaron Guo Answer: 350 Solution: The probability that the rank N player passes round i (where i = 0 is implied as 1) is i 1024 − 2 N − 1 . 1023 N − 1 Summing this from i = 0 to 9 (each represents the expectation of advancing one round) we must find the minimum N for which the sum goes below 2 . Let r indicate N − 1 . 1023 − r The first term is 1 , the second simplifies to , and round i ’s contribution is 1023 i 2 − 2 Y 1023 − r − j . 1023 − j j =0 At this point, a program may output N = 350 . However, one may notice that for larger i, this term vanishes; in fact, estimating this product with i 2 − 1 1023 − r k where k = . 1023 The trailing terms in the product will be a bit smaller than k, but vanishes. If we do find the estimate P i 9 2 − 1 for k where k = 2 , k will be a bit to small, the true k being something slightly greater. i =0 The main concern is how many great of an upper limit for i we choose to approximate with for k. If 2 3 we stop at i = 2 , for instance, we have 1 + k + k = 2 , where we might find k = a just estimate, 3 2 8
- being just shy of 1 . We may produce/cursory check 0 . 67 or 0 . 68 as an estimate for k (from this 3 27 equation, around 0 . 683). This produces N = 339 or N = 328 . 3 7 Estimating the real solution to 1 + k + k + k = 2 produces very close to the maximum number of 2 128 7 points. Given our estimate for k , just above , we can estimate that k ≈ ≈ 0 . 06 . 1 3 2187 3 Then, we estimate the solution to k + k = 1 − 0 . 06 , for which we might notice that if k = k − δ, then 1 by Newton’s method, we can approximate k by 4 2 δ · (1 + 3 k ) ≈ δ · 1 + 3 · = 0 . 06 , 9 0 . 06 · 3 making δ about ≈ 0 . 026 . If this is subtracted from k = 0 . 683 , then k = 0 . 657 , producing 1 7 N = 351 .