HMMT 二月 2014 · 冲刺赛 · 第 33 题
HMMT February 2014 — Guts Round — Problem 33
题目详情
- [ 25 ] An up-right path from ( a, b ) 2 R to ( c, d ) 2 R is a finite sequence ( x , y ) , . . . , ( x , y ) of 1 1 k k 2 points in R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1 i < k we have that either 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 number between 0 and 1. If C is the actual answer to this question and A is your answer, then your score on this problem is d max { 25(1 10 | C A | ) , 0 } e .
解析
- [ 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 k 2 points in R such that ( a, b ) = ( x , y ), ( c, d ) = ( x , y ), and for each 1 ≤ i < k we have that either 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 number between 0 and 1. If C is the actual answer to this question and A is your answer, then your score on this problem is d max { 25(1 − 10 | C − A | ) , 0 }e . Answer: 0 . 2937156494680644 . . . Note that any up-right path must pass through exactly one point of the form ( n, − n ) (i.e. a point on the upper-left to lower-right diagonal), and the number of such ( ) ( ) 2 800 800 paths is because there are up-right paths from ( − 400 , − 400) to ( n, − n ) and another 400 − n 400 − n ( ) 800 from ( n, − n ) to (400 , 400). An up-right path contains a point ( x, y ) with | x | , | y | ≤ 10 if and 400 − n only 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 400 800 800 n = − 400 400 − n ( ) 800 To estimate this, recall that if we normalize to be a probability density function, then it will n 1 be approximately normal with mean 400 and variance 800 · = 200. If this is squared, then it is 4 proportional to a normal distribution with half the variance and the same mean, because the probability 2 ( x − μ ) − 2 2 2 σ density function of a normal distribution is proportional to e , where μ is the mean and σ is the variance. ( ) 2 800 Therefore, the probability density function is roughly proportional to a normal distribution with n ( ) ∑ 2 10 800 mean 400 and variance 100, or standard deviation 10. So represents roughly one n = − 10 400 − n standard deviation. Recall that approximately 68 percent of a normal distribution lies within one standard deviation of the mean (look up the 68-95-99.7 rule to read more), so a good guess would be around .32. This guess can be improved by noting that we’re actually summing 21 values instead of 21 20, so you’d have approximately . 68 · ≈ . 71 of the normal distribution, giving an answer of . 29. 20