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 + 1 nan +1
for all positive integers n . If a = 30, how many possible values can a take? (For a real number x ,n
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 + 1 nan +1
for all positive integers n . If a = 30, how many possible values can a take? (For a real number x ,n
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 recurrencen n +1
⌊ ⌋
b + 1
b = n .nn +1
It has the property that b is divisible by n . Rearranging the recurrence, we see thatnnb b + 1 bn +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 largesti n +1 n n +1
∗
possible value of b (call this b ) is the smallest multiple of n which is at least b . Also, sincen n +1
∗ ∗ ∗ ∗nb = 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, sincen
⌈ ⌉n
∗
n +1 b
∗
b = n ,
we findnn
⌈ ⌉
⌈ ⌉
n + 1 cn +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 .
n 1