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

英文解析

34. [ 25 ] Consider a number line, with a lily pad placed at each integer point. A frog is standing at thelily 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 pointn + 2 or point n + 3 on the number line. Each of the lily pads at the points 1 , · · · , 2013 on the numberline has, independently and with probability 1 / 2, a snake. Let p be the probability that the frog canmake 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 isd 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 frogcan reach the lily pad at the point 2014 on the number line if it is allowed to jump from a point non 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 pointn 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 lilypad 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 mm =1
    Then, it can be shown by induction that a is the number of possible arrangements of snakes on lilympads 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 approximatelym +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 toroughly 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 apolynomial. 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. (Itturns 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 problemusing 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
    2 = 8 possible states for this Markov chain, because each of the lily pads at positions n − 2 , n − 1 , n can 3
    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 timein = 0, the lily pad at point n is reachable ( d = 1) whereas the lily pads at points n − 1 and n − 2 areunreachable ( d = d = 0), so the Markov chain is in state number 1 + d + 2 d + 4 d = 5.0
    1 2 2 1 0
    The transition matrix M for the Markov chain can now be computed directly from the conditions ofthe problem. It is equal to
     
    1 0 0 0 0 0 01
     12
    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 vfor the Markov chain at time 2013 is
    2014 tv := 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 probabilityp = [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 equalto the second-largest real eigenvalue of the matrix M . The characteristic polynomial of M is
    3 4 6 7
    λ 3 λ λ 3 λdet( λI − M ) = − + + − + λ ,8
    8 8 4 2
    so its eigenvalues are the roots of this polynomial. The largest real root of this characteristic polynomialis λ = 1, and the second-largest real root is 0 . 9105247383471604 . . . (which can be found, again, using
    Newton’s method, after factoring out ( λ − 1) λ from the polynomial), which is a good approximation 3
    for p .