HMMT 十一月 2019 · 冲刺赛 · 第 35 题
HMMT November 2019 — Guts Round — Problem 35
题目详情
- [20] You are trying to cross a 400 foot wide river. You can jump at most 4 feet, but you have many stones you can throw into the river. You will stop throwing stones and cross the river once you have placed enough stones to be able to do so. You can throw straight, but you can’t judge distance very well, so each stone ends up being placed uniformly at random along the width of the river. Estimate the expected number N of stones you must throw before you can get across the river. ⌊ ⌋ ( ) 3 N E An estimate of E will earn 20 min , points. E N
解析
- [20] You are trying to cross a 400 foot wide river. You can jump at most 4 feet, but you have many stones you can throw into the river. You will stop throwing stones and cross the river once you have placed enough stones to be able to do so. You can throw straight, but you can’t judge distance very well, so each stone ends up being placed uniformly at random along the width of the river. Estimate the expected number N of stones you must throw before you can get across the river. ⌊ ⌋ ( ) 3 N E An estimate of E will earn 20 min , points. E N Proposed by: Carl Schildkraut and Milan Haiman Answer: 712 . 811 If we divide the river into 100 4-foot sections, then to be able to cross we need to get at least one stone into each section. On average, this takes 100 100 100
-
- · · · + ≈ 100 ln 100 100 99 1 100 stone throws (it takes moves on average to get a stone into a new section if k sections already 100 − k have a stone). So the answer is at least 100 ln 100 ≈ 450. On the other hand, if we divide the river into 200 2-foot sections, then once we have a stone in each section we are guaranteed to be able to cross. By a similar argument, we obtain that the answer is at most 200 ln 200 ≈ 1050. Estimates near these bounds earn about 5 to 7 points. An estimate in between can earn close to 20 points. To compute the answer (almost) exactly, we use the following argument. Scale the problem so the river is of size 1, and the jumps are of size 0 . 01. Suppose that after n throws, the stones thrown are located at positions 0 < x < x < · · · < x < 1 . Let x = 0 , x = 1 , r = 0 . 01 . 1 2 n 0 n +1 Define P ( n ) to be the probability that you still cannot cross the river after n throws. In other words, ∑ ∞ there exists i such that x − x > r. Then our answer is P ( n ) . i +1 i n =0 By PIE we can write ( ) ∞ ∑ n + 1 i − 1 n P ( n ) = ( − 1) max(1 − ir, 0) . i i =1 based on which intervals x − x have length greater than r. Now we switch the order of summation: i +1 i ( ) ( ) ∞ ∞ ∞ ∞ ∞ ∑ ∑ ∑ ∑ ∑ n + 1 n + 1 i − 1 n i − 1 n P ( n ) = ( − 1) max(1 − ir, 0) = ( − 1) max(1 − ir, 0) . i i n =0 n =0 i =1 i =1 n =0 Let x = max(1 − ir, 0) . Then ( ) ( ) ∞ ∞ i − 1 ∑ ∑ n + 1 i + j x n i − 1 j x = x x = . i +1 i i (1 − x ) n =0 j =0 Thus, our answer is b 1 /r c i − 1 ∑ (1 − ir ) i − 1 ( − 1) ≈ 712 . 811 , i +1 ( ir ) i =1 where the last approximation uses the C++ code below. #include <bits/stdc++.h> using namespace std; typedef long double ld; int main() { ld sum = 0, r = 0.01; for (int i = 1; ; ++i) { ld x = 1-r*i; if (x <= 0) break; ld ex = pow(x/(1-x),i-1)/(1-x)/(1-x); if (i&1) sum += ex; else sum -= ex; } cout << fixed << setprecision(8) << sum; }