Maths Olympiad Prep

Library / /1 of 18

Algebra Difficulty 4.4 AIME Prove it United States

Problem:

Prove that no integer greater than 20082008 can be equal to the sum of squares of its digits.

Solution

Solution:

Let n=akak1a0n = \overline{a_k a_{k-1} \ldots a_0} be an integer equal to the sum of squares of its own digits. Then
n=10kak+10k1ak1++a0. n = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + a_0.
On the other hand,
a02+a12++ak292(k+1)=81(k+1)<10kfor k4. a_0^2 + a_1^2 + \cdots + a_k^2 \leq 9^2 \cdot (k+1) = 81 \cdot (k+1) < 10^k \quad \text{for } k \geq 4.
(The last inequality is easy to prove by induction because it holds for k=4k=4, and if it holds for some kk, then
81(k+2)=81(k+1)+8110k+81<10k+10k<10k+1. 81 \cdot (k+2) = 81 \cdot (k+1) + 81 \leq 10^k + 81 < 10^k + 10^k < 10^{k+1}.
)

Therefore, for k4k \geq 4, the sum of squares of the digits is less than 10k10^k, so nn cannot have more than 44 digits. Thus, n9999n \leq 9999.

Now, for n2009n \geq 2009, nn must be a 44-digit number. The maximum sum of squares of 44 digits is 4×81=3244 \times 81 = 324, which is much less than 20092009. Therefore, no integer greater than 20082008 can be equal to the sum of squares of its digits.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.