Maths Olympiad Prep

Library / /75 of 75

Number theory Difficulty 7.2 National Olympiad, round 2 Prove it Italy

Problem:
Given any positive integer nn, we call the cyclostyled of nn the number obtained by concatenating 2012 writings of nn (in base 10). For example the cyclostyled of 314 is 314314314314314314314 \ldots 314, where the digits "314" repeat 2012 times.
a) Determine all positive integers mm such that the cyclostyled of mm is a multiple of 9.
b) Determine all positive integers mm such that the cyclostyled of mm is a multiple of 11.

Solution

Solution:
Let f(n)f(n) be the cyclostyled of nn.

a.
Let us call s(m)s(m) the sum of the digits of mm. By the divisibility criterion for 9 we have that f(n)f(n) is a multiple of 9 if and only if s(f(n))s(f(n)) is a multiple of 9; on the other hand s(f(n))=2012s(n)s(f(n)) = 2012 \cdot s(n), which is a multiple of 9 if and only if s(n)s(n) is (because the greatest common divisor between 2012 and 9 is equal to 1). Using again the divisibility criterion for 9 we observe that s(n)s(n) is a multiple of 9 if and only if nn is.

In conclusion the nn sought are all and only the multiples of 9.

b.
Let us call r(m)r(m) the alternating sum of the digits of mm (done in such a way that the units digit is taken with a positive sign). By the divisibility criterion for 11 we have that f(n)f(n) is a multiple of 11 if and only if r(f(n))r(f(n)) is a multiple of 11.

We distinguish the following two cases.

- nn has an even number of digits.

Then r(f(n))=2012r(n)r(f(n)) = 2012 \cdot r(n), indeed each digit of nn is summed 2012 times with the same sign. Since GCD(2012,11)=1\operatorname{GCD}(2012,11) = 1 we observe that 2012r(n)2012 \cdot r(n) is a multiple of 11 if and only if r(n)r(n) is. Using again the divisibility criterion for 11 we have that r(n)r(n) is a multiple of 11 if and only if nn is.

Therefore the nn with an even number of digits that we want are all and only the multiples of 11.

- nn has an odd number of digits.

In the alternating sum of the digits of f(n)f(n) we have that each digit of nn is summed 20122\frac{2012}{2} times with the sign ++ and just as many times with the sign -; therefore r(f(n))=0r(f(n)) = 0, that is, f(n)f(n) is always a multiple of 11.

In conclusion the nn sought are the positive integers with an odd number of digits and the multiples of 11 with an even number of 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 translated into English from it; metadata (topic, difficulty) added by this project.