HMMT 十一月 2010 · 冲刺赛 · 第 23 题

HMMT November 2010 — Guts Round — Problem 23

[ 12 ] Let a , a , . . . be an infinite sequence of positive integers such that for integers n > 2, a = 1 2 n 2012 3 a − 2 a . How many such sequences { a } are there such that a ≤ 2 ? n − 1 n − 2 n 2010 1

解析

[ 12 ] Let a , a , . . . be an infinite sequence of positive integers such that for integers n > 2, a = 1 2 n 2012 3 a − 2 a . How many such sequences { a } are there such that a ≤ 2 ? n − 1 n − 2 n 2010 2009 Answer: 36 · 2 + 36 Consider the characteristic polynomial for the recurrence a − 3 a + n +2 n +1 2 2 a = 0, which is x − 3 x + 2. The roots are at 2 and 1, so we know that numbers a must be of n i i − 1 2009 the form a = a 2 + b for integers a and b . Therefore a must equal to a 2 + b , where a and i 2010 b are both integers. If the expression is always positive, it is sufficient to say a is positive and a is 1 nonnegative, or a + b > 0, and a ≥ 0. 2012 2009 2012 2009 For a given value of a , 1 − a ≤ b ≤ 2 − a 2 , so there are 2 − a 2 + a possible values of b for 3 each a (where the quantity is positive). a can take any value between 0 and 2 , we sum over all such a 2012 2009 in this range, to attain 9 · 2 − (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)2 + (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8), ( ) 2009 or 36 2 + 36 , which is our answer. 1