HMMT 十一月 2013 · THM 赛 · 第 10 题

英文解析

10. [ 8 ] Find the sum of all positive integers n such that there exists an integer b with | b | 6 = 4 such that the base − 4 representation of n is the same as the base b representation of n .
    Answer: 1026 All 1 digit numbers, 0 , 1 , 2 , 3, are solutions when, say, b = 5. (Of course, d ∈
    { 0 , 1 , 2 , 3 } works for any base b of absolute value greater than d but not equal to 4.)
    Consider now positive integers n = ( a . . . a a ) with more than one digit, so d ≥ 1, a 6 = 0, andd 1 0 4 d
    0 ≤ a ≤ 3 for k = 0 , 1 , . . . , d . Then n has the same representation in base b if and only if | b | > max ak k
    ∑ ∑ ∑
    d d dk k k kand a ( − 4) = a b , or equivalently, a ( b − ( − 4) ) = 0.
    k k kk =0 k =0 k =0
    k k
    First we prove that b ≤ 3. Indeed, if b ≥ 4, then b 6 = 4 = ⇒ b ≥ 5, so b − ( − 4) is positive for all
    ∑
    k k d ddk ≥ 1 (and zero for k = 0). But then a ( b − ( − 4) ) ≥ a ( b − ( − 4) ) must be positive, andk dk =0
    cannot vanish.
    Next, we show b ≥ 2. Assume otherwise for the sake of contradiction; b cannot be 0 , ± 1 (thesebases don’t make sense in general) or − 4, so we may label two distinct negative integers − r, − s with
    ∑
    k kdr − 1 ≥ s ≥ 2 such that { r, s } = { 4 , − b } , s > max a , and a (( − r ) − ( − s ) ) = 0, which,
    k kk =0
    k kcombined with the fact that r − s ≥ 0 (equality only at k = 0), yieldsd − 1
    ∑
    d d d d d − 1 − k k kr − s ≤ a ( r − s ) = ( − 1) a ( r − s )
    d kk =0
    d − 1
    ∑dr − 1
    k k d
    ≤ ( s − 1)( r − s ) = ( s − 1) − ( s − 1) .
    r − 1
    k =0
    d dr − 1 r − 1
    d d
    Hence r − 1 ≤ ( s − 1) < ( r − 1) = r − 1, which is absurd.
    r − 1 r − 1
    Thus b ≥ 2, and since b ≤ 3 we must either have b = 2 or b = 3. In particular, all a must be at mostkb − 1. We now rewrite our condition asd − 1
    ∑
    d d d − 1 − k k ka (4 − ( − b ) ) = ( − 1) a (4 − ( − b ) ) .
    d kk =0
    k k
    Since 4 − ( − b ) ≥ 0 for k ≥ 0, with equality only at k = 0, we deduce
    ∑
    d d k ka (4 − ( − b ) ) ≤ ( b − 1)(4 − ( − b ) ) .
    k ≡ d − 1 (mod 2)d
    If d − 1 is even ( d is odd), this givesd +1 0 d +1 0
    4 − 4 b − bd da (4 + b ) ≤ ( b − 1) − ( b − 1) ,
    2 2 d
    4 − 1 b − 1
    d +1
    4 15
    so 4 < ( b − 1) = ⇒ b > 1 + , which is impossible.d
    15 4
    Thus d − 1 is odd ( d is even), and we getd +1 1 d +1 1 d 4
    a − ( b − 1)
    4 − 4 b − b b − 1
    d d 15 da (4 − b ) ≤ ( b − 1) + ( b − 1) ⇐⇒ ≥ .
    2 2 d bd
    4 − 1 b − 1 4 − 1
    a +
    b +1 dd
    1 2 − 1 11
    If b = 2, then a = 1, so = ≥ , which is clearly impossible ( d ≥ 2).
    d d d
    2 +1 4 − 1 25
    d/ 2
    9 − 1 8
    If b = 3 and a = 2, then ≤ . Since d is even, it’s easy to check this holds only for d/ 2 = 1,
    d d/ 2
    16 − 1 15
    with equality, so a = b − 1 if k ≡ d − 1 (mod 2). Thus ( a , . . . , a ) = (2 , 2 , a ), yielding solutionsk d 0 0
    (22 x ) (which do work; note that the last digit doesn’t matter).
    d/ 23
    9 − 1 4
    Otherwise, if b = 3 and a = 14, then ≤ . It’s easy to check d/ 2 ∈ { 1 , 2 } .
    d/ 2 d
    16 − 115
    If d/ 2 = 1, we’re solving 16 a − 4 a + a = 9 a + 3 a + a ⇐⇒ a = a . We thus obtain the working
    2 1 0 2 1 0 2 1
    solution (11 x ) . (Note that 110 = 220 in bases − 4 , 3.)1
    If d/ 2 = 2, we want 256 a − 64 a +16 a − 4 a + a = 81 a +27 a +9 a +3 a + a , or 175 = 91 a − 7 a +7 a ,23
    4 3 2 1 0 4 3 2 1 0 3 2 1
    which simplifies to 25 = 13 a − a + a . This gives the working solutions (1210 x ) , (1221 x ) . (Note
    3 2 1 3 3
    2 2
    that 12100 = 110 and 12210 = 110 + 110 in bases − 4 , 3.)
    The list of all nontrivial ( ≥ 2-digit) solutions (in base − 4 and b ) is then 11 x , 22 x , 1210 x , 1221 x , where
    2 2
    b = 3 and x ∈ { 0 , 1 , 2 } . In base 10, they are 12 + x , 2 · 12 + x , 12 + x , 12 + 12 + x , with sum
    3(2 · 12 + 4 · 12) + 4(0 + 1 + 2) = 1020.2
    Finally, we need to include the trivial solutions n = 1 , 2 , 3, for a total sum of 1026.