Maths Olympiad Prep

Library / /3 of 31

Number theory Difficulty 7.8 National olympiad, round 2 Prove it Baltic Way

Prove that there are infinitely many positive integers nn, which are not divisible by 1010 and such that s(n2)<s(n)5s(n^2) < s(n) - 5 where s(n)s(n) is the sum of digits of nn.

Solution

All integers of the form 49999499\ldots99 satisfy the condition. Indeed, if n=49999k=510k1n = 4\underbrace{99\ldots99}_{k} = 5 \cdot 10^k - 1 then
n2=25102k10k+1+1=24999k10000k1. n^2 = 25 \cdot 10^{2k} - 10^{k+1} + 1 = 24 \underbrace{99\ldots9}_{k-1} \underbrace{00\ldots00}_{k} 1.
In such a case s(n)=4+9ks(n) = 4 + 9k, but s(n2)=7+9(k1)=9k2s(n^2) = 7 + 9(k - 1) = 9k - 2.

Solution:
Consider a sequence 103m102m110^{3m} - 10^{2m} - 1. Similarly to the original solution it is easy to check that if mm increases by 11 then s(n)s(n) increases by 2727, but s(n2)s(n^2) increases by 1818 only.

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 and solution reproduced as published; topic and difficulty added by this site.