HMMT 二月 2006 · TEAM1 赛 · 第 15 题

英文解析

15. [50] Find, with proof, all positive integer palindromes whose square is also a palindrome.
    Answer: A palindrome satisfies the requirement if and only if the sum of the squaresof its digits is less than 10. We may categorize these numbers this way:
    • 3
    • Any palindromic combination of 1 s and 0 s with at most nine 1 s.
    • Any palindrome consisting of a single 2 in the middle and 1 s and 0 s elsewhere,8
    with at most four 1 s.
    • 2000 . . . 0002
    • 2000 . . . 0001000 . . . 0002
    ∑di
    Solution: Let n := a · 10 be a palindrome, where the a are digits with a = ai i i d − ii =0
    and a 6 = 0. Then, if we letd
    ∑
    b := a ak i ji + j = kfor all 0 ≤ k ≤ 2 d , then
    2 d
    ∑
    2 kn = b · 10
    k =0 k
    (this is not necessarily the decimal expansion of n , however). We have to show that 2
    ∑
    2 2 da < 10 if and only if n is a palindrome.
    i =0 i
    ∑
    2 d
    Suppose a < 10. Then, by the AM-GM inequality, we haveii =0
    d d
    2 2 2
    ∑ ∑ ∑ ∑2
    a + a aa 10 10
    i j jib = a a ≤ ≤ + < + = 10 .
    k i j
    2 2 2 2 2
    i =0 j =0
    i + j = k i + j = k
    Thus, loosely speaking, no carrying is ever done in computing n × n by long multik 2
    plication, so the digit in the 10 place in n is precisely b , and it’s easy to see thatk
    2 2
    b = b and that b = a 6 = 0. So n is indeed a palindrome, as desired.
    k 2 d − k 2 dd
    ∑
    2 d
    Now suppose a ≥ 10. Here note thatii =0
    d d
    ∑ ∑ ∑
    b = a a = a a = a ≥ 10 .2
    d i j i d − iii =0 i =0
    i + j = dk 2
    Thus, it cannot be true that, for all k , b represents the 10 digit of n , because nokdigit can be greater than or equal to 10. Let be the greatest such that b does not
2 2 represent the 10 digit of n . We are trying to prove that n cannot be a palindrome. Consider three cases: • a = a ≥ 4. In this case we must have ≥ 2 d , because b = a > 10.2
    d 0 2 dd
    2 2 d 2 d
    If a = 4, then n ends in the digit 6, but lies in the interval [16 · 10 , 25 · 10 ),
    and so starts with either a 1 or a 2; thus, n cannot be a palindrome. Similarly,20
    2 2
    if a = 5, then n ends in 5 but starts with 2 or 3; if a = 6, then n ends in 6
    0 0
    but starts with 3 or 4; if a = 7, then n ends in 9 but starts with 4, 5, or 6; if 2
    2 20
    a = 8, then n ends in 4 but starts with 6, 7 or 8; if a = 9, then n ends in 1
    0 0
    but starts with 8 or 9.
    • ` ≥ 2 d and a = a ≤ 3.
    d 0
    Here we do something similar, but with a slight twist. The units digit of n is 2
    2 2 2 2 d 2 2 da . Because ` ≥ 2 d , n must be in the interval [( a + 1) · 10 , ( a + 1) · 10 ),
    0 00
    2 2 d 2 2 d +19
    which is certainly a subset of the interval [( a + 1) · 10 , a · 10 ). No integer
    0 0
    2 2
    in even this larger interval manages to start with the digit a , so n cannot bepalindromic.0
    • ` < 2 d .
    Here we can rest assured that n does have (2 d + 1) digits — that is, the first 2
    2 d 2 kdigit is in the 10 place. In order for n to be a palindrome, the digits in the 10
    2 d − kand 10 places must always be the same.
    Now b , b , . . . , b had all better be less than 10, or else ` would be greater than
    ` ` +1 2 dwhat it is. Thus, the numbers just listed do appear as the lowest digits of n in 2
    left-to-right order, although they don’t appear as the highest (2 d + 1 − ` ) digits
    2 2
    of n in right-to-left order. Thus, n cannot be a palindrome.
    10