HMMT 十一月 2022 · 冲刺赛 · 第 35 题

HMMT November 2022 — Guts Round — Problem 35

[20] For each i ∈ { 1 , . . . , 10 } , a is chosen independently and uniformly at random from [0 , i ]. Let P be i the probability that a < a < · · · < a . Estimate P . 1 2 10 E P An estimate of E will earn ⌊ 20 min( , ) ⌋ points. P E

解析

[20] For each i ∈ { 1 , . . . , 10 } , a is chosen independently and uniformly at random from [0 , i ]. Let P i be the probability that a < a < · · · < a . Estimate P . 1 2 10 E P An estimate of E will earn ⌊ 20 min( , ) ⌋ points. P E Proposed by: Gabriel Wu Answer: P ≈ 0 . 003679 Solution: The probability that a > a is 7 / 8. The probability that a > a is 7 / 9. The probability 2 1 3 2 that a > a is 23 / 32. The probability that a > a is 17 / 25. The probability that a > a is 47 / 72. 4 3 5 4 6 5 The probability that a > a is 31 / 49. The probability that a > a is 79 / 128. The probability that 7 6 8 7 a > a is 49 / 81.The probability that a > a is 119 / 200. 9 8 10 9 Assuming all of these events are independent, you can multiply the probabilities together to get a probability of around 0 . 05. However, the true answer should be less because, conditioned on the realization of a < a < · · · < a , the value of a is on average large for its interval. This makes 1 2 k k a < a less likely. Although this effect is small, when compounded over 9 inequalities we can k k +1 estimate that it causes the answer to be about 1 / 10 of the fully independent case. 9 P was approximated with 10 simulations (the answer is given with a standard deviation of about − 6 2 × 10 ).