HMMT 二月 2011 · 冲刺赛 · 第 25 题
HMMT February 2011 — Guts Round — Problem 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 ≤ n and | x − y | ≤ 3. Let A be the number of paths from (0 , 0) to ( n, n ) that consist only of steps of the n form ( x, y ) → ( x, y + 1) and ( x, y ) → ( x + 1 , y ) and are contained entirely within R . Find the smallest A n +1 positive real number that is greater than for all n . A n
解析
- [ 14 ] Let n be an integer greater than 3. Let R be the set of lattice points ( x, y ) such that 0 ≤ x, y ≤ n and | x − y | ≤ 3. Let A be the number of paths from (0 , 0) to ( n, n ) that consist only of steps of the n form ( x, y ) → ( x, y + 1) and ( x, y ) → ( x + 1 , y ) and are contained entirely within R . Find the smallest A n +1 positive real number that is greater than for all n . A n √ 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 b n n n be the number of ways to get to the point ( n + 1 , n + 2). By symmetry, a is also the number of ways n to get to ( n + 3 , n ) and b is also the number of ways to get to the point ( n + 2 , n + 1). n a 1 a b 0 1 b b 0 1 b a 0 1 a 0 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 + b i +1 i i b = a + 3 b i +1 i i We have both 3 a = 3 a + 3 b and a = a + b . Subtracting these gives i +1 i i i +2 i +1 i +1 a − 3 a = a − 3 a + b − 3 b i +2 i +1 i +1 i i +1 i a − 3 a = a − 3 a + a i +2 i +1 i +1 i i a = 4 a − 2 a i +2 i +1 i 2 Now we can solve this recurrence using its characteristic polynomial x − 4 x + 2, which has roots of √ √ √ √ i i 2 + 2 and 2 − 2. We can then write a = A (2 + 2) + B (2 − 2) for some constants A and B . i Now, a = a and a = a + b = 4. Using this, we solve for A and B to get 0 1 0 0 ( ) ( ) √ √ √ √ 1 + 2 1 − 2 i i a = (2 + 2) + (2 − 2) i 2 2 Then, b = a − a i 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, the n n − 1 √ √ A A n n ratio approaches 2 + 2. Hence the least upper bound of is 2 + 2. A A n − 1 n − 1