IMO 1998 SL 20

Origin: ARG

Problem

Prove that for each positive integer n, there exists a positive integer with the following properties: (i) It has exactly n digits. (ii) None of the digits is 0. (iii) It is divisible by the sum of its digits.

Solution

We first consider the special case n = 3r. Then the simplest choice 10n−1

11 . . . 1 (n digits) works. This can be shown by induction: it is true for r = 1, while the inductive step follows from 103r −1 = (103r−1 −1)(102\cdot3r−1 + 103r−1 + 1), because the second factor is divisible by 3. In the general case, let k \geqn/2 be a positive integer and a1, . . . , an−k be nonzero digits. We have

A = (10k −1)a1a2 . . . an−k = a1a2 . . . an−k−1a′ n−k 99 . . . 99    2k−n b1b2 . . . bn−k−1b′ n−k, where a′ n−k = an−k −1, bi = 9 −ai, and b′ n−k = 9 −a′ n−k. The sum of digits of A equals 9k independently of the choice of digits a1, . . . , an−k. Thus we need only choose k \geqn 2 and digits a1, . . . , an−k−1 ̸\in{0, 9} and an−k \in{0, 1} in order for the conditions to be fulfilled. Let us choose k = . 3r, if 3r < n \leq2 \cdot 3r for some r \inZ, 2 \cdot 3r, if 2 \cdot 3r < n \leq3r+1 for some r \inZ; and a1a2 . . . an−k = 22 . . .2. The number A = 22 . . . 2    n−k−1 1 99 . . .99    2k−n 77 . . . 7    n−k−1 thus obtained is divisible by 2 \cdot (10k −1), which is, as explained above, divisible by 18\cdot 3r. Finally, the sum of digits of A is either 9 \cdot 3r or 18 \cdot 3r; thus A has the desired properties.