HMMT 十一月 2020 · GEN 赛 · 第 10 题
HMMT November 2020 — GEN Round — Problem 10
题目详情
- A sequence of positive integers a , a , a , . . . satisfies 1 2 3 ⌊ ⌋ a n a = n + 1 n +1 n for all positive integers n . If a = 30, how many possible values can a take? (For a real number x , 30 1 b x c denotes the largest integer that is not greater than x .)
解析
- A sequence of positive integers a , a , a , . . . satisfies 1 2 3 ⌊ ⌋ a n a = n + 1 n +1 n for all positive integers n . If a = 30, how many possible values can a take? (For a real number x , 30 1 b x c denotes the largest integer that is not greater than x .) Proposed by: Carl Joshua Quines Answer: 274 Solution: It is straightforward to show that if a = 1, then a = n for all n . Since a is an 1 n n +1 increasing function in a , it follows that the set of possible a is of the form { 1 , 2 , . . . , m } for some m , n 1 which will be the answer to the problem. Consider the sequence b = a − 1, which has the recurrence n n +1 ⌊ ⌋ b + 1 n b = n . n +1 n It has the property that b is divisible by n . Rearranging the recurrence, we see that n b b + 1 b n +1 n n +1 ≤ < + 1 , n + 1 n + 1 n + 1 and as the b are integers, we get b − 1 ≤ b < b + n . For n ≥ 2, this means that the largest i n +1 n n +1 ∗ possible value of b (call this b ) is the smallest multiple of n which is at least b . Also, since n n +1 n ∗ ∗ ∗ ∗ b = b + 1, we find b = b − 1, meaning that the largest value for a is b , and thus the answer is b . 1 0 1 0 1 1 1 ∗ ∗ We have now derived a procedure for deriving b from b = 29. To speed up the computation, let 1 29 ∗ c = b /n . Then, since n n ⌈ ⌉ ∗ b n +1 ∗ b = n , n n we find ⌈ ⌉ ⌈ ⌉ n + 1 c n +1 c = c = c + . n n +1 n +1 n n We now start from c = 1 and wish to find c . 29 1 Applying the recurrence, we find c = 2, c = 3, and so on until we reach c = 15. Then, d c /n e 28 27 15 n +1 becomes greater than 1 and we find c = 17, c = 19, and so on until c = 23. The rest can be done 14 13 11 manually, with c = 26, c = 29, c = 33, c = 38, c = 45, c = 54, c = 68, c = 91, c = 137, and 10 9 8 7 6 5 4 3 2 ∗ c = 274. The last few steps may be easier to perform by converting back into the b . 1 n