返回题库

HMMT 十一月 2020 · GEN 赛 · 第 10 题

HMMT November 2020 — GEN Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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 .)
解析

英文解析

  1. 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