返回题库

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

HMMT November 2019 — Guts Round — Problem 35

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [20] You are trying to cross a 400 foot wide river. You can jump at most 4 feet, but you have many stonesyou can throw into the river. You will stop throwing stones and cross the river once you have placedenough stones to be able to do so. You can throw straight, but you can’t judge distance very well, soeach stone ends up being placed uniformly at random along the width of the river. Estimate the expectednumber N of stones you must throw before you can get across the river.
    ⌊ ⌋
    ( )
    N E3
    An estimate of E will earn 20 min , points.
    E N
解析

英文解析

  1. [20] You are trying to cross a 400 foot wide river. You can jump at most 4 feet, but you have manystones you can throw into the river. You will stop throwing stones and cross the river once you haveplaced enough stones to be able to do so. You can throw straight, but you can’t judge distance verywell, so each stone ends up being placed uniformly at random along the width of the river. Estimatethe expected number N of stones you must throw before you can get across the river.
    ⌊ ⌋
    ( )
    N E3
    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 stoneinto each section. On average, this takes
    100 100 100 + + · · · + ≈ 100 ln 100
    100 99 1
    stone throws (it takes moves on average to get a stone into a new section if k sections already 100
    100 − khave 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 eachsection we are guaranteed to be able to cross. By a similar argument, we obtain that the answer is atmost 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 in =0
    By PIE we can write
    ( )
    ∞
    ∑
    n + 1
    i − 1 n
    P ( n ) = ( − 1) max(1 − ir, 0) .
    i =1 ibased 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 in =0 n =0 i =1 i =1 n =0
    Let x = max(1 − ir, 0) . Then
    ( ) ( )
    ∞ ∞
    i − 1
    ∑ ∑
    n + 1 i + j xn i − 1 jx = x x = .
    i +1
    i i (1 − x )
    n =0
    j =0
    Thus, our answer isb 1 /r ci − 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;
    }