Olympiad Maths Prep

Library / /25 of 28

Number theory Difficulty 6.3 National olympiad Prove it Ukraine

a) Consider the square of the numbers 11, 22, \ldots, 20092009 written one after another in some random order as one number. Is it possible to obtain a perfect square of an integer in this way?

b) Consider the numbers 11, 22, \ldots, 20092009 written one after another in some random order as one number. Is it possible to obtain a perfect square of an integer in this way?

Solution

a) Consider remainders of these squares divided by 33. In the big number which we have generated each square can be represented as k210nk^2 \cdot 10^n, and the big number is the sum of such terms. If k2l(mod3)k^2 \equiv l \pmod{3} then k210nl(mod3)k^2 \cdot 10^n \equiv l \pmod{3}. It is well-known that k20(mod3)k^2 \equiv 0 \pmod{3} is equivalent to 3k3|k, and k21(mod3)k^2 \equiv 1 \pmod{3} is equivalent to 3k3 \nmid k. There are 669669 numbers from 11 to 20092009 that are divisible by 33, and 13401340 there are not. As 13402(mod3)1340 \equiv 2 \pmod{3} the remainder of the big number modulo 33 is 22, which is impossible for a perfect square, which completes the proof.

b) Consider remainders of these numbers divided by 99. In the big number which we have generated each number can be represented as k10nk \cdot 10^n, and the big number is the sum of such terms. kl(mod9)k \equiv l \pmod{9} if and only if k10nl(mod9)k \cdot 10^n \equiv l \pmod{9}. Thus we need to find the sum of the remainders which equals to the sum of all digits of the big number. If we break the number into the groups of nine 11, 22, \ldots, 99; 1010, 1111, \ldots, 1818; \ldots, 19991999, 20002000, \ldots, 20072007, then the sum of the numbers in each group is divisible by 99. The sum of the remaining numbers 20082008 and 20092009 is divisible by 33 but is not divisible by 99, which is impossible for a perfect square.

Looking for a route rather than 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.