HMMT 二月 2016 · COMB 赛 · 第 6 题
HMMT February 2016 — COMB Round — Problem 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 = n a − 1 if a 6 = 0 n − 1 n − 1 A non-negative integer d is said to be jet-lagged if there are non-negative integers r, s and a positive integer n such that d = r + s and that a = a + s . How many integers in { 1 , 2 , . . . , 2016 } are n + r n jet-lagged?
解析
- 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 = n a − 1 if a 6 = 0 n − 1 n − 1 A non-negative integer d is said to be jet-lagged if there are non-negative integers r, s and a positive integer n such that d = r + s and that a = a + s . How many integers in { 1 , 2 , . . . , 2016 } are n + r n jet-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 M and a ≥ a . N M Divide the a into the following “blocks”: i • a = 1, a = 0, 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 k and so on. The k block contains a for 2 < i ≤ 2 . It’s easy to see by induction that a k = 0 and i 2 k thus a k = 2 − 1 for all k ≥ 1. Within each block, the value a + n is constant, and for the k th n 2 +1 k block ( k ≥ 1) it equals 2 . Therefore, d = ( a + N ) − ( a + M ) is the difference of two powers of 2, N M n m n th say 2 − 2 . For any n ≥ 1, it is clear there exists an N such that a + N = 2 (consider the n N m block). We can guarantee a ≥ a by setting M = 2 . Therefore, we are searching for the number N M n m of integers between 1 and 2016 that can be written as 2 − 2 with n ≥ m ≥ 1. The pairs ( n, m ) with n m n > m ≥ 1 and n ≤ 10 all satisfy 1 ≤ 2 − 2 ≤ 2016 (45 possibilities). In the case that n = 11, we n m m have that 2 − 2 ≤ 2016 so 2 ≥ 32, so m ≥ 5 (6 possibilities). There are therefore 45 + 6 = 51 jetlagged numbers between 1 and 2016.