Maths Olympiad Prep

Library / /35 of 36

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it Netherlands

An \ell-code is an integer n0n \ge 0 of at most \ell digits, if necessary supplemented by leading zeros, so that it consists of \ell digits in total. Thus, you can make a 4-code out of 310 by writing it as 0310. An \ell-code is called self-squared if the last \ell digits of the square of that code form exactly the original \ell-code. Thus, the 1-codes 5 and 6 are self-squared, but the 3-code 006 is not self-squared, because 62=36=0366^2 = 36 = 036 does not end in 006. The 2-code 76 is self-squared, because 762=577676^2 = 5776 ends in 76.

a. Prove that an \ell-code nn is self-squared if and only if n(n1)n(n-1) is divisible by 1010^\ell.

b. Prove that any self-squared \ell-code n2n \ge 2 ends in the digit 5 or the digit 6.

c. Prove that any self-squared \ell-code n2n \ge 2 is extendable to a self-squared (+1)(\ell+1)-code in exactly one way by placing a digit in front of it.

d. It follows from (b) and (c) that for every \ell, there exist exactly two self-squared \ell-codes m,n2m, n \ge 2. What is their sum m+nm+n (in terms of \ell)?

Solution

a. Suppose that nn is a self-squared \ell-code. Then the last \ell digits of n2n=n(n1)n^2 - n = n(n - 1) are all zeros. This means that n(n1)n(n - 1) is divisible by 1010^\ell. Vice versa, nn is self-squared if n2nn^2 - n is divisible by 1010^\ell and thus ends in \ell zeros.

b. The number n(n1)n(n - 1) is divisible by 10 and so, in particular, it is divisible by 5. This means that one of the numbers nn and n1n - 1 must be divisible by 5. In other words, the last digit of either nn or n1n - 1 must be a 0 or 5. So the only possible final digits for nn are 0, 1, 5 and 6.
If the last digit of nn is 0, then n1n - 1 is not divisible by 2 or 5. Since n(n1)n(n - 1) is divisible by 10=2510^\ell = 2^\ell \cdot 5^\ell and there can be no factors 2 or 5 in n1n - 1, nn must be divisible by 1010^\ell. But that means that the last \ell digits of nn, which are all the digits of nn, must all be zeros. Then we get n=0n = 0, which is smaller than 2.
If the last digit of nn is a 1, then nn is not divisible by 2 or 5. Since n(n1)n(n - 1) is divisible by 10=2510^\ell = 2^\ell \cdot 5^\ell and there can be no factors 2 or 5 in nn, n1n - 1 must be divisible by 1010^\ell. But that means that the last \ell digits of n1n - 1, which are all the digits of n1n - 1, must all be zeros. Then we get n=1n = 1, which is smaller than 2.
So all self-quadratic codes n2n \ge 2 end in a 5 or 6.

c. Suppose that m=c10+nm = c \cdot 10^\ell + n is an (+1)(\ell + 1)-code obtained by putting cc in front of nn. Because of (a), mm is self-squared if and only if
m(m1)=(c10+n)(c10+n1)=c2102+c10(2n1)+n(n1) m(m-1) = (c \cdot 10^{\ell} + n)(c \cdot 10^{\ell} + n-1) = c^2 \cdot 10^{2\ell} + c \cdot 10^{\ell}(2n-1) + n(n-1)
is divisible by 10+110^{\ell+1}. As 1\ell \ge 1, the term c2102c^2 \cdot 10^{2\ell} is also divisible by 10+110^{\ell+1}. The number n(n1)n(n-1) is divisible by 1010^\ell, because of part (a), and can therefore be written as d10d \cdot 10^\ell. It then follows that
c10(2n1)+d10=10(c(2n1)+d) c \cdot 10^{\ell}(2n - 1) + d \cdot 10^{\ell} = 10^{\ell} \cdot (c(2n - 1) + d)
must be divisible by 10+110^{\ell+1}, or in other words that c(2n1)+dc(2n - 1) + d must be divisible by 10.
Because of part (b), nn must end in a 5 or 6. If nn ends in a 5, then 2n12n-1 is a multiple of ten minus one, i.e. it is of the shape 10k110k-1, and we see that c(10k1)+dc(10k-1)+d must be divisible by 10 and so c+d-c+d must be divisible by 10. On the other hand, if nn ends in a 6, then 2n12n-1 is a multiple of ten plus one, say 10k+110k+1, and we see that c(10k+1)+dc(10k+1)+d must be divisible by 10 and so c+dc+d must be divisible by 10.
In both cases, there is a unique possibility for cc from the numbers 0, 1, 2, ..., 9 for which c+d-c+d (or c+dc+d) is divisible by 10, since, of the ten consecutive numbers 0+d,1+d,...,9+d-0+d, -1+d, ..., -9+d (or 0+d,1+d,...,9+d0+d, 1+d, ..., 9+d), exactly one is divisible by 10. Therefore, there is a unique digit cc that we can put before the \ell-code nn such that mm is a self-squared (+1)(\ell+1)-code.

d. Suppose that n2n \ge 2 is a self-squared \ell-code. Then we will show that k=10+1nk = 10^\ell + 1 - n is also a self-squared \ell-code. Because n2n \ge 2, we have k101k \le 10^\ell - 1 and kk can thus really be written using \ell digits. From part (a) it follows that kk is self-squared if and only if
k(k1)=(10+1n)(10n)=102+10(12n)+(n1)n k(k-1) = (10^{\ell} + 1 - n)(10^{\ell} - n) = 10^{2\ell} + 10^{\ell}(1 - 2n) + (n-1)n
is divisible by 1010^\ell. The first two terms are always divisible by 1010^\ell and (n1)n(n-1)n is divisible by 1010^\ell because nn is self-squared. So it follows that kk is self-squared.
Since n101n \le 10^\ell - 1, we have k2k \ge 2. Furthermore, 10+110^\ell + 1 is odd, and so one out of nn and kk is even and the other number is odd. In particular, nn and kk are thus not equal to each other. Since there are exactly two self-squared \ell-codes 2\ge 2, the other self-squared \ell-code mm must be equal to kk. It then holds that m+n=k+n=10+1m+n=k+n=10^\ell+1.

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.