Maths Olympiad Prep

Library / /13 of 23

Number theory Difficulty 5.7 AIME, harder Prove it Ireland

Determine, with proof, the smallest positive multiple of 9999 all of whose digits are either 11 or 22.

Solution

We call a number *eligible* if its digits are all either 11 or 22. A number is divisible by 99=91199 = 9 \cdot 11 if and only if it is divisible by both 99 and 1111. Suppose NNN \in \mathbb{N} has base-10 expansion anan1a2a1a_n a_{n-1} \dots a_2 a_1. We define three digit-sums (full, odd, even):
S(N):=1inai,o(N):=1ini oddai,e(N):=1ini evenai. S(N) := \sum_{1 \le i \le n} a_i, \quad o(N) := \sum_{\substack{1 \le i \le n \\ i \text{ odd}}} a_i, \quad e(N) := \sum_{\substack{1 \le i \le n \\ i \text{ even}}} a_i.

As is well known (and easily established), NN is divisible by 99 if and only if S(N)S(N) is divisible by 99, while NN is divisible by 1111 if and only if d(N):=o(N)e(N)d(N) := o(N) - e(N) is divisible by 1111.

Suppose first that S(N)=9S(N) = 9. Then NN has at least five digits,
3o(N)92=7,2e(N)93=6, 3 \le o(N) \le 9 - 2 = 7, \quad 2 \le e(N) \le 9 - 3 = 6,
and o(N)o(N), e(N)e(N) are of opposite parity. Consequently, 0<d(N)50 < |d(N)| \le 5, and so NN cannot be divisible by 1111.

Thus, we must have S(N)18S(N) \ge 18 for eligible NN to be divisible by 9999. Suppose next that S(N)=18S(N) = 18. To minimize eligible NN with S(N)=18S(N) = 18, we must certainly minimize the number of digits in NN. We immediately rule out nine 22s, since then d(N)=108d(N) = 10 - 8 is not divisible by 1111.

The next smallest number of digits involves picking eight 22s and two 11s. The smallest such number is the one with 11s in the leading positions, i.e. N=1122222222N = 1122222222. Then o(N)=e(N)=9o(N) = e(N) = 9, and NN is divisible by 1111, and hence by 9999. Thus, this is the minimal example with S(N)=18S(N) = 18.

It remains only to consider eligible numbers NN with S(N)27S(N) \ge 27. Such numbers have at least 1414 digits, so are larger than the one we found above. Thus, the minimal number is indeed 11222222221122222222.

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.