HMMT 二月 2016 · COMB 赛 · 第 6 题

英文解析

6. Define the sequence a , a . . . as follows: a = 1 and for every n ≥ 2,
   1 2 1
   {
   n − 2 if a = 0
   n − 1
   a =
   a − 1 if a 6 = 0 nn − 1 n − 1
   A non-negative integer d is said to be jet-lagged if there are non-negative integers r, s and a positiveinteger n such that d = r + s and that a = a + s . How many integers in { 1 , 2 , . . . , 2016 } aren + r njet-lagged?
   Proposed by: Pakawut Jiradilok
   Let N = n + r , and M = n . Then r = N − M , and s = a − a , and d = r + s = ( a + N ) − ( a + M ).
   N M N M
   So we are trying to find the number of possible values of ( a + N ) − ( a + M ), subject to N ≥ M
   N Mand a ≥ a .
   N M
   Divide the a into the following “blocks”:
   • a = 1, a = 0,i
   1 2
   • a = 1, a = 0,
   3 4
   • a = 3, a = 2, a = 1, a = 0,
   5 6 7 8
   • a = 7, a = 6, . . . , a = 0,
   9 10 16
   th k − 1 kand so on. The k block contains a for 2 < i ≤ 2 . It’s easy to see by induction that a k = 0 and
   2 ikthus a k = 2 − 1 for all k ≥ 1. Within each block, the value a + n is constant, and for the k thn
   2 +1
   block ( k ≥ 1) it equals 2 . Therefore, d = ( a + N ) − ( a + M ) is the difference of two powers of 2,k
   N Mn m n thsay 2 − 2 . For any n ≥ 1, it is clear there exists an N such that a + N = 2 (consider the nblock). We can guarantee a ≥ a by setting M = 2 . Therefore, we are searching for the numberm n
   N Mn mof integers between 1 and 2016 that can be written as 2 − 2 with n ≥ m ≥ 1. The pairs ( n, m ) withn mn > m ≥ 1 and n ≤ 10 all satisfy 1 ≤ 2 − 2 ≤ 2016 (45 possibilities). In the case that n = 11, wen m mhave that 2 − 2 ≤ 2016 so 2 ≥ 32, so m ≥ 5 (6 possibilities). There are therefore 45 + 6 = 51
   jetlagged numbers between 1 and 2016.