HMMT 二月 2014 · 冲刺赛 · 第 33 题

英文解析

33. [ 25 ] An up-right path from ( a, b ) ∈ R to ( c, d ) ∈ R is a finite sequence ( x , y ) , . . . , ( x , y ) of
    1 1 k kpoints in R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1 ≤ i < k we have that either 2
    1 1 k k
    ( x , y ) = ( x + 1 , y ) or ( x , y ) = ( x , y + 1).
    i +1 i +1 i i i +1 i +1 i i
    Let S be the set of all up-right paths from ( − 400 , − 400) to (400 , 400). What fraction of the paths in
    S do not contain any point ( x, y ) such that | x | , | y | ≤ 10? Express your answer as a decimal numberbetween 0 and 1.
    If C is the actual answer to this question and A is your answer, then your score on this problem isd max { 25(1 − 10 | C − A | ) , 0 }e .
    Answer: 0 . 2937156494680644 . . . Note that any up-right path must pass through exactly one pointof the form ( n, − n ) (i.e. a point on the upper-left to lower-right diagonal), and the number of such
    ( ) ( )
    800 8002
    paths is because there are up-right paths from ( − 400 , − 400) to ( n, − n ) and another
    400 − n 400 − n
    ( )
    from ( n, − n ) to (400 , 400). An up-right path contains a point ( x, y ) with | x | , | y | ≤ 10 if and 800
    400 − nonly if − 10 ≤ n ≤ 10, so the probability that this happens is
    ( ) ( )
    ∑ ∑
    2 2
    10 10
    800 800
    n = − 10 n = − 10
    400 − n 400 − n = ( )
    ( )
    ∑
    2 1600
    800400
    n = − 400800
    400 − n
    ( )
    To estimate this, recall that if we normalize to be a probability density function, then it will 800
    1 nbe approximately normal with mean 400 and variance 800 · = 200. If this is squared, then it isproportional to a normal distribution with half the variance and the same mean, because the probability 4
    ( x − μ )2
    2−
    2 σ2
    density function of a normal distribution is proportional to e , where μ is the mean and σ isthe variance.
    ( )
    8002
    Therefore, the probability density function is roughly proportional to a normal distribution withn
    ( )
    ∑
    800102
    mean 400 and variance 100, or standard deviation 10. So represents roughly onen = − 10
    400 − nstandard deviation. Recall that approximately 68 percent of a normal distribution lies within onestandard deviation of the mean (look up the 68-95-99.7 rule to read more), so a good guess would bearound .32. This guess can be improved by noting that we’re actually summing 21 values instead of
    20, so you’d have approximately . 68 · ≈ . 71 of the normal distribution, giving an answer of . 29.21
    20