HMMT 十一月 2013 · THM 赛 · 第 10 题
HMMT November 2013 — THM Round — Problem 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 .
解析
- [ 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, and d 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 a k k ∑ ∑ ∑ d d d k k k k and a ( − 4) = a b , or equivalently, a ( b − ( − 4) ) = 0. k k k k =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 ∑ d k k d d k ≥ 1 (and zero for k = 0). But then a ( b − ( − 4) ) ≥ a ( b − ( − 4) ) must be positive, and k d k =0 cannot vanish. Next, we show b ≥ 2. Assume otherwise for the sake of contradiction; b cannot be 0 , ± 1 (these bases don’t make sense in general) or − 4, so we may label two distinct negative integers − r, − s with ∑ d k k r − 1 ≥ s ≥ 2 such that { r, s } = { 4 , − b } , s > max a , and a (( − r ) − ( − s ) ) = 0, which, k k k =0 k k combined with the fact that r − s ≥ 0 (equality only at k = 0), yields d − 1 ∑ d d d d d − 1 − k k k r − s ≤ a ( r − s ) = ( − 1) a ( r − s ) d k k =0 d − 1 d ∑ r − 1 k k d ≤ ( s − 1)( r − s ) = ( s − 1) − ( s − 1) . r − 1 k =0 d d r − 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 most k b − 1. We now rewrite our condition as d − 1 ∑ d d d − 1 − k k k a (4 − ( − b ) ) = ( − 1) a (4 − ( − b ) ) . d k k =0 k k Since 4 − ( − b ) ≥ 0 for k ≥ 0, with equality only at k = 0, we deduce ∑ d d k k a (4 − ( − b ) ) ≤ ( b − 1)(4 − ( − b ) ) . d k ≡ d − 1 (mod 2) If d − 1 is even ( d is odd), this gives d +1 0 d +1 0 4 − 4 b − b d d a (4 + b ) ≤ ( b − 1) − ( b − 1) , d 2 2 4 − 1 b − 1 d +1 4 15 d so 4 < ( b − 1) = ⇒ b > 1 + , which is impossible. 15 4 Thus d − 1 is odd ( d is even), and we get 4 d +1 1 d +1 1 d a − ( b − 1) 4 − 4 b − b b − 1 d d d 15 a (4 − b ) ≤ ( b − 1) + ( b − 1) ⇐⇒ ≥ . d 2 2 d b 4 − 1 b − 1 4 − 1 a + d b +1 d 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 solutions k d 0 0 (22 x ) (which do work; note that the last digit doesn’t matter). 3 d/ 2 9 − 1 4 Otherwise, if b = 3 and a = 14, then ≤ . It’s easy to check d/ 2 ∈ { 1 , 2 } . d d/ 2 15 16 − 1 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 1 solution (11 x ) . (Note that 110 = 220 in bases − 4 , 3.) 3 2 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 , 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 2 3(2 · 12 + 4 · 12) + 4(0 + 1 + 2) = 1020. Finally, we need to include the trivial solutions n = 1 , 2 , 3, for a total sum of 1026.