HMMT 二月 2014 · 冲刺赛 · 第 34 题
HMMT February 2014 — Guts Round — Problem 34
题目详情
- [ 25 ] Consider a number line, with a lily pad placed at each integer point. A frog is standing at the lily pad at the point 0 on the number line, and wants to reach the lily pad at the point 2014 on the number line. If the frog stands at the point n on the number line, it can jump directly to either point n + 2 or point n + 3 on the number line. Each of the lily pads at the points 1 , · · · , 2013 on the number line has, independently and with probability 1 / 2, a snake. Let p be the probability that the frog can make some sequence of jumps to reach the lily pad at the point 2014 on the number line, without ever 1 / 2014 landing on a lily pad containing a snake. What is p ? Express your answer as a decimal number. 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 20 | C A | ) , 0 } e .
解析
- [ 25 ] Consider a number line, with a lily pad placed at each integer point. A frog is standing at the lily pad at the point 0 on the number line, and wants to reach the lily pad at the point 2014 on the number line. If the frog stands at the point n on the number line, it can jump directly to either point n + 2 or point n + 3 on the number line. Each of the lily pads at the points 1 , · · · , 2013 on the number line has, independently and with probability 1 / 2, a snake. Let p be the probability that the frog can make some sequence of jumps to reach the lily pad at the point 2014 on the number line, without ever 1 / 2014 landing on a lily pad containing a snake. What is p ? Express your answer as a decimal number. 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 − 20 | C − A | ) , 0 }e . Answer: 0.9102805441016536 First, we establish a rough upper bound for the probability p . Let q be the probability that the frog can reach the lily pad at the point 2014 on the number line if it is allowed to jump from a point n on the number line to the point n + 1, in addition to the points n + 2 and n + 3. Clearly, p ≤ q . Furthermore, p is approximated by q ; it should be easy to convince one’s self that jumps from a point n to the point n + 1 are only useful for reaching the lily pad at point 2014 in very few situations. Now we compute q . We note that, if the frog can jump from points n to points n + 1, n + 2, and n + 3, then it can reach the lily pad at the point 2014 on the number line if and only if each snake-free lily pad is at most 3 units away from the closest snake-free lily pad on the left. ∞ Define the sequence { a } by a = 1, a = 1, a = 2, and a = a + a + a for m ≥ 0. m 0 1 2 m +3 m +2 m +1 m m =1 Then, it can be shown by induction that a is the number of possible arrangements of snakes on lily m pads at points 1 , · · · , m − 1 so that the frog can make some sequence of jumps (of size 1, 2, or 3) from the lily pad at point 0 to the lily pad at point m without landing on a lily pad containing a snake. It 2013 follows that q = a / 2 . So 2014 1 / 2014 1 / 2014 1 / 2014 2013 / 2014 1 / 2014 p ≈ q = ( a ) / 2 ≈ ( a ) / 2 . 2014 2014 1 / 2014 Analyzing the recurrence relation a = a + a + a yields that ( a ) is approximately m +3 m +2 m +1 m 2014 3 2 equal to the largest real root r of the characteristic polynomial equation r − r − r − 1 = 0. So to roughly approximate p , it suffices to find the largest real root of this equation. For this, we apply Newton’s method, or one of many other methods for computing the roots of a polynomial. With an initial guess of 2, one iteration of Newton’s method yields r ≈ 13 / 7, so p ≈ r/ 2 ≈ 13 / 14 ≈ 0 . 928571. A second iteration yields r ≈ 1777 / 966, so p ≈ r/ 2 ≈ 1777 / 1932 ≈ 0 . 919772. (It turns out that the value of r is 1 . 839286 . . . , yielding p ≈ r/ 2 = 0 . 919643 . . . .) Using tools from probability theory, we can get an even better estimate for p . We model the problem using a discrete-time Markov chain. The state of the Markov chain at time n , for n = 0 , 1 , . . . , 2013, indicates which of the lily pads at positions n − 2 , n − 1 , n are reachable by the frog. It is clear that the state of the Markov chain at time n only depends (randomly) on its state at time n − 1. There are 3 2 = 8 possible states for this Markov chain, because each of the lily pads at positions n − 2 , n − 1 , n can be either reachable or unreachable by the frog. Number each state using the number 1 + d + 2 d + 4 d , 2 1 0 where d is 1 if the lily pad at point n − i is reachable, and 0 otherwise. So, for example, at time i n = 0, the lily pad at point n is reachable ( d = 1) whereas the lily pads at points n − 1 and n − 2 are 0 unreachable ( d = d = 0), so the Markov chain is in state number 1 + d + 2 d + 4 d = 5. 1 2 2 1 0 The transition matrix M for the Markov chain can now be computed directly from the conditions of the problem. It is equal to 1 1 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 2 1 0 1 0 0 0 0 0 2 1 0 0 0 0 0 0 0 2 M := . 1 1 0 0 0 0 0 0 2 2 1 1 0 0 0 0 0 0 2 2 1 1 0 0 0 0 0 0 2 2 1 1 0 0 0 0 0 0 2 2 (The verification of this transition matrix is left as an exercise for the reader.) So the state vector v for the Markov chain at time 2013 is 2014 t v := M [0 , 1 , 0 , 0 , 0 , 0 , 0 , 0] . Now, the lily pad at point 2014 is reachable by the frog if and only if the Markov chain is in state 3 , 4 , 5 , 6 , 7, or 8 at time 2013. This happens with probability p = [0 , 0 , 1 , 1 , 1 , 1 , 1 , 1] v. t 1 / 2014 By expanding [0 , 1 , 0 , 0 , 0 , 0 , 0 , 0] in an eigenbasis for M , we find that p is approximately equal to the second-largest real eigenvalue of the matrix M . The characteristic polynomial of M is 3 4 6 7 λ 3 λ λ 3 λ 8 det( λI − M ) = − + + − + λ , 8 8 4 2 so its eigenvalues are the roots of this polynomial. The largest real root of this characteristic polynomial is λ = 1, and the second-largest real root is 0 . 9105247383471604 . . . (which can be found, again, using 3 Newton’s method, after factoring out ( λ − 1) λ from the polynomial), which is a good approximation for p .