Maths Olympiad Prep

Library / /53 of 101

Number theory Difficulty 6.1 National olympiad Prove it Estonia

Call a positive integer nn interesting if both the sum of digits of nn and the sum of digits of n+1n+1 are perfect squares, whereas nn and n+1n+1 have the same number of digits. Find all positive integers kk for which there exists an interesting kk-digit number.

Solution

For any positive integer aa, let s(a)s(a) denote the sum of digits of aa. Clearly s(n+1)=s(n)+1s(n + 1) = s(n) + 1 unless the last digit of n+1n + 1 is zero. The only two consecutive integers that are both perfect squares are 00 and 11, but s(n)=0s(n) = 0 is impossible for a positive nn. The contradiction shows that the last digit of n+1n + 1 must be 00 and the last digit of nn must be 99.

Let nn be an interesting positive integer that ends with exactly mm digits 99. Clearly s(n)s(n+1)=9m1s(n) - s(n + 1) = 9m - 1. Note that a perfect square is congruent to 00, 11, 44 or 77 modulo 99. As s(n)s(n+1)=9m18(mod9)s(n) - s(n + 1) = 9m - 1 \equiv 8 \pmod 9, we must have s(n)0(mod9)s(n) \equiv 0 \pmod 9 and s(n+1)1(mod9)s(n + 1) \equiv 1 \pmod 9. But s(n+1)=1s(n + 1) = 1 is impossible, because this would require n+1n + 1 to be a power of 1010, in the case of which nn and n+1n + 1 would not consist of the same number of digits. Thus s(n+1)82=64s(n + 1) \ge 8^2 = 64, as 828^2 is the next smallest perfect square congruent to 11 modulo 99. But as s(n)>s(n+1)s(n) > s(n + 1), we have s(n)92=81s(n) \ge 9^2 = 81. This implies that nn must contain at least 99 digits. Containing exactly 99 digits would be possible only if nn consisted entirely of nines, but in such case n+1n + 1 would contain one more digit. Hence nn must contain at least 1010 digits.

Consider now the 1010-digit number n=788888899n = 788888899. In this case m=2m = 2, s(n)=81=92s(n) = 81 = 9^2 and s(n+1)=8192+1=64=82s(n + 1) = 81 - 9 \cdot 2 + 1 = 64 = 8^2, thus nn is interesting. Inserting zeros between 77 and 88 does not influence s(n)s(n) and s(n+1)s(n + 1). So we can obtain an mm-digit interesting number for every m10m \ge 10.

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.