HMMT 二月 2002 · 团队赛 · 第 3 题

HMMT February 2002 — Team Round — Problem 3

[40] Suppose that a positive integer n has the property that n , 2 n , 3 n , . . . , 9 n are all palindromes. Prove that the decimal digits of n are all zeros or ones. Floor functions. The notation b x c stands for the largest integer less than or equal to x .

解析

[40] Suppose that a positive integer n has the property that n , 2 n , 3 n , . . . , 9 n are all palindromes. Prove that the decimal digits of n are all zeros or ones. Solution. First consider the ones digit a of n ; we claim that a = 1. Certainly a cannot be even, for then 5 n would be divisible by 10. If a is 5, 7, or 9, then 2 n has an even ones digit, while its most significant digit is 1. If a is 3, then 4 n has an even ones digit but most significant digit 1. Thus a = 1 is the only possibility. Moreover 9 n has the same number of digits as n , for otherwise 9 n would have most significant digit 1 but least significant digit 9, which is forbidden. Now suppose n has at least one digit that is neither a zero nor a one. Let b be the leftmost (i.e., most significant) such digit, so that the left end of the decimal representation of n looks like a . . . a b . . . 1 r for some r ≥ 1 and digits a ∈ { 0 , 1 } . When n is multiplied by 9, there will be a carry out of the i th column containing b . In particular, the r digit from the left in 9 n will not be 9 a . But the right r end of the decimal representation of n is . . . a . . . a ; r 1 th because each a is 0 or 1, there are no carries out of the first r − 1 columns, so the r digit from the i right in 9 n will be 9 a . Thus 9 n is not a palindrome, a contradiction. This completes the proof. r 1 Floor functions. The notation b x c stands for the largest integer less than or equal to x .