HMMT 二月 2006 · TEAM1 赛 · 第 15 题
HMMT February 2006 — TEAM1 Round — Problem 15
题目详情
- [50] Find, with proof, all positive integer palindromes whose square is also a palindrome. 2
解析
- [50] Find, with proof, all positive integer palindromes whose square is also a palin-
drome.
Answer: A palindrome satisfies the requirement if and only if the sum of the squares
of its digits is less than 10. We may categorize these numbers this way:
• 3
• Any palindromic combination of 1s and 0s with at most nine 1s.
8
• Any palindrome consisting of a single 2 in the middle and 1s and 0s elsewhere,
with at most four 1s.
• 2000 . . . 0002
• 2000 . . . 0001000 . . . 0002
d
∑
i
Solution: Let n := a · 10 be a palindrome, where the a are digits with a = a
i i i d − i
i =0
and a 6 = 0. Then, if we let
d
∑
b := a a
k i j
i + j = k
for all 0 ≤ k ≤ 2 d , then
2 d
∑
2 k
n = b · 10
k
k =0
2
(this is not necessarily the decimal expansion of n , however). We have to show that
∑
d
2 2
a < 10 if and only if n is a palindrome.
i
i =0
∑
d
2
Suppose a < 10. Then, by the AM-GM inequality, we have
i
i =0
d d
2 2 2
2
∑ ∑ ∑ ∑
a + a a
a 10 10
i j j
i
b = 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 multi-
k 2
plication, so the digit in the 10 place in n is precisely b , and it’s easy to see that
k
2 2
b = b and that b = a 6 = 0. So n is indeed a palindrome, as desired.
k 2 d − k 2 d
d
∑
d
2
Now suppose a ≥ 10. Here note that
i
i =0
d d
∑ ∑ ∑
2
b = a a = a a = a ≥ 10 .
d i j i d − i
i
i =0 i =0
i + j = d
k 2
Thus, it cannot be true that, for all k , b represents the 10 digit of n , because no
k
digit can be greater than or equal to 10. Let
be the greatest such that b does not2 2 represent the 10 digit of n . We are trying to prove that n cannot be a palindrome. Consider three cases: 2 • a = a ≥ 4. In this case we must have≥ 2 d , because b = a > 10. d 0 2 d d 2 2 d 2 d If a = 4, then n ends in the digit 6, but lies in the interval [16 · 10 , 25 · 10 ), 0 2 and so starts with either a 1 or a 2; thus, n cannot be a palindrome. Similarly, 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 2 but starts with 3 or 4; if a = 7, then n ends in 9 but starts with 4, 5, or 6; if 0 2 2 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 2 Here we do something similar, but with a slight twist. The units digit of n is 2 2 2 2 d 2 2 d a . Because ` ≥ 2 d , n must be in the interval [( a + 1) · 10 , ( a + 1) · 10 ), 0 0 0 9 2 2 d 2 2 d +1 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 be 0 palindromic. • ` < 2 d . 2 Here we can rest assured that n does have (2 d + 1) digits — that is, the first 2 d 2 k digit is in the 10 place. In order for n to be a palindrome, the digits in the 10 2 d − k and 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 d 2 what it is. Thus, the numbers just listed do appear as the lowest digits of n in 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