Maths Olympiad Prep

Library / /376 of 860

Number theory Difficulty 5.1 AIME, harder Find the answer

Determine the number of four-digit integers nn such that nn and 2n2n are both palindromes.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n=abban=\underline{a} \underline{b} \underline{b} \underline{a}. If a,b4a, b \leq 4 then there are no carries in the multiplication n×2n \times 2, and 2n=(2a)(2b)(2b)(2a)2n=(2a)(2b)(2b)(2a) is a palindrome. We shall show conversely that if nn and 2n2n are palindromes, then necessarily a,b4a, b \leq 4. Hence the answer to the problem is 4×5=204 \times 5=\mathbf{20} (because aa cannot be zero). If a5a \geq 5 then 2n2n is a five-digit number whose most significant digit is 1, but because 2n2n is even, its least significant digit is even, contradicting the assumption that 2n2n is a palindrome. Therefore a4a \leq 4. Consequently 2n2n is a four-digit number, and its tens and hundreds digits must be equal. Because a4a \leq 4, there is no carry out of the ones place in the multiplication n×2n \times 2, and therefore the tens digit of 2n2n is the ones digit of 2b2b. In particular, the tens digit of 2n2n is even. But if b5b \geq 5, the carry out of the tens place makes the hundreds digit of 2n2n odd, which is impossible. Hence b4b \leq 4 as well.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.