IMO 1990 SL 20

Origin: POL

Problem

Prove that every integer k greater than 1 has a multiple that is less than k4 and can be written in the decimal system with at most four different digits.

Solution

Let n be the unique integer such that 2n−1 \leqk < 2n. Let S(n) be the set of numbers less than 10n that are written with only the digits {0, 1} in the decimal system. Evidently |S(n)| = 2n > k and hence there exist two numbers x, y \inS(n) such that k | x −y. Let us show that w = |x −y| is the desired number. By definition k | w. We also have w < 1.2 \cdot 10n−1 \leq1.2 \cdot (23\sqrt 2)n−1 \leq1.2 \cdot k3\sqrt k \leqk4. Finally, since x, y \inS(n), it follows that w = |x −y| can be written using only the digits {0, 1, 8, 9}. This completes the proof.