Maths Olympiad Prep

Library / /27 of 35

Number theory Difficulty 6.0 National olympiad Prove it Slovenia

Find all positive integers nn for which there exists a multiple of 1111 with the sum of its digits equal to nn.

Solution

Denote the sum of the digits of a positive integer mm by S(m)S(m). Then S(11)=2S(11) = 2. We notice that for the first few multiples of 1111 the sum of the digits is always even. The first multiple for which the sum of the digits is odd is 209=1911209 = 19 \cdot 11 and this sum is 1111. Using these two examples we can construct multiples of 1111 with the sum of the digits equal to nn for almost all positive integers nn.

The number of the form 111111\dots11 with 1111 repeated kk times in a row is divisible by 1111 and the sum of the digits is 2k2k. Hence, for all even nn there exists a multiple of 1111 with the sum of its digits equal to nn.

As we have just seen we can get the sum of 1111 from 209209. Any number of the form 209111120911\dots11 with 209209 followed by kk repetitions of 1111 is divisible by 1111 and the sum of its digits is 11+2k11 + 2k. So, for all odd integers nn greater than or equal to 1111, there exists a multiple of 1111 with the sum of the digits equal to nn.

The only positive integers still in question are 11, 33, 55, 77 and 99. Let us show that in these cases we cannot find multiples of 1111 with the required sum of digits.

Let mm be a multiple of 1111. Assume that S(m)9S(m) \le 9. Let LL denote the sum of the digits of mm in the odd positions and let DD be the sum of the digits in the even positions. Since S(m)=L+DS(m) = L + D, we have L,D9L, D \le 9. The criterion for divisibility by 1111 implies that LDL - D is divisible by 1111, but on the other hand we have 9DLDL9-9 \le -D \le L - D \le L \le 9. So, LD=0L - D = 0 or L=DL = D. We conclude that S(m)=L+D=2DS(m) = L + D = 2D is even and no multiple of 1111 can have the sum of its digits equal to 11, 33, 55, 77 or 99.

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.