HMMT 二月 2023 · 冲刺赛 · 第 34 题
HMMT February 2023 — Guts Round — Problem 34
题目详情
- [25] The number 2027 is prime. For i = 1, 2, . . . , 2026, let p be the smallest prime number such that i p ≡ i (mod 2027). Estimate max( p , . . . , p ). i 1 2026 8 8 Submit a positive integer E . If the correct answer is A , you will receive b 25 min(( E/A ) , ( A/E ) ) c points. (If you do not submit a positive integer, you will receive zero points for this question.)
解析
- [25] The number 2027 is prime. For i = 1, 2, . . . , 2026, let p be the smallest prime number such that i p ≡ i (mod 2027). Estimate max( p , . . . , p ). i 1 2026 8 8 Submit a positive integer E . If the correct answer is A , you will receive b 25 min(( E/A ) , ( A/E ) ) c points. (If you do not submit a positive integer, you will receive zero points for this question.) Proposed by: Luke Robitaille, Brian Liu, Maxim Li, Misheel Otgonbayar, Sean Li, William Wang Answer: 113779 Solution: In this solution, all logs are in base e . Let p , p , . . . be the primes in sorted order. Let 1 2 q = p mod 2027. Since the residues of primes modulo 2027 should be uniformly distributed, we can i i make the probabilistic approximation that the q are random variables uniformly distributed among i 1 , . . . , 2026. This becomes the famous ”coupon collector” problem: the random variables q are coupons i with 2026 different types, and we keep collecting coupons until we have encountered one of each type. In other words, we seek to find the smallest k such that { q , . . . , q } = { 1 , . . . , 2026 } , and then the 1 k answer to the problem is p . k 1 1 1 It is known that the expected value of k is 2026( + + · · · + ) ≈ 2026 log 2026. This is because we 1 2 2026 2026 2026 must draw an expected coupons until we get our first distinct coupon type, then an expected 2026 2025 coupons until we get our second new coupon type, and so on. The standard deviation of k is a small fraction of its its expectation, so we can safely assume that k is approximately 2026 log 2026. Since the n -th prime is approximately n log n , our estimate is E ≈ 2026 log 2026 log(2026 log 2026) 2 ≈ 2026 log 2026 ≈ 117448 This achieves A/E ≈ 0 . 969, which scores 19 out of 25 points.