HMMT 二月 2011 · 冲刺赛 · 第 25 题

英文解析

25. [ 14 ] Let n be an integer greater than 3. Let R be the set of lattice points ( x, y ) such that 0 ≤ x, y ≤ nand | x − y | ≤ 3. Let A be the number of paths from (0 , 0) to ( n, n ) that consist only of steps of theform ( x, y ) → ( x, y + 1) and ( x, y ) → ( x + 1 , y ) and are contained entirely within R . Find the smallestnn +1Apositive real number that is greater than for all n .
    √n a
    Answer: 2 + 2
    We first find A in terms of n . Let a be the number of ways to get to the point ( n, n + 3), and let bn n nbe the number of ways to get to the point ( n + 1 , n + 2). By symmetry, a is also the number of waysnto get to ( n + 3 , n ) and b is also the number of ways to get to the point ( n + 2 , n + 1).
    1 ana b
    0 1
    b b
    0 1
    b a
    0 1
    0 a
    Guts Round
    We can easily see that a = 1 and b = 3. This also means that A = a + 3 b + 3 b + a =
    0 0 n n − 3 n − 3 n − 3 n − 3
    2 a + 6 b .
    n − 3 n − 3
    We also get the recurrence:
    a = a + bi +1 i ib = a + 3 bi +1 i i
    We have both 3 a = 3 a + 3 b and a = a + b . Subtracting these givesi +1 i i i +2 i +1 i +1
    a − 3 a = a − 3 a + b − 3 bi +2 i +1 i +1 i i +1 ia − 3 a = a − 3 a + ai +2 i +1 i +1 i ia = 4 a − 2 ai +2 i +1 i
    Now we can solve this recurrence using its characteristic polynomial x − 4 x + 2, which has roots of 2
    √ √ √ √
    i i
    2 + 2 and 2 − 2. We can then write a = A (2 + 2) + B (2 − 2) for some constants A and B .
    Now, a = a and a = a + b = 4. Using this, we solve for A and B to geti
    0 1 0 0
    ( ) ( )
    √ √
    √ √
    1 + 2 1 − 2
    i ia = (2 + 2) + (2 − 2)
    2 2 i
    Then,
    b = a − ai i +1 i
    ( ) ( )
    √ √
    √ √ √ √
    1 + 2 1 − 2
    i +1 i i +1 i = ((2 + 2) − (2 + 2) ) + ((2 − 2) − (2 − 2) )
    2 2
    ( ) ( )
    √ √
    √ √ √ √
    1 + 2 1 − 2
    i i = (1 + 2)(2 + 2) + (1 − 2)(2 − 2)
    2 2
    ( ) ( )
    √ √
    √ √
    3 + 2 2 3 − 2 2
    i i = (2 + 2) + (2 − 2)
    2 2
    Therefore,
    √ √ √ √
    n − 3 n − 3
    A = 2 a + 6 b = (10 + 7 2)(2 + 2) + (10 − 7 2)(2 − 2) .
    n n − 3 n − 3
    √ √
    We can then easily see that A < (2 + 2) A . Also, since 2 − 2 < 1, as n approaches infinity, then n − 1
    √ √
    A An nratio approaches 2 + 2. Hence the least upper bound of is 2 + 2.
    A An − 1 n − 1