31st IMO shortlist 1990/20 solution

31st IMO 1990 shortlist

Problem 20

Show that every positive integer n > 1 has a positive multiple less than n⁴ which uses at most 4 different digits.

Solution

Solution by Demetres Christofides

Take m such that 2^m-1 ≤ n < 2^m. There are 2^m > n numbers with m digits or less and whose digits are all 0 or 1, so (pigeonhole principle) two of them must be equal mod n. So their difference is divisible by n and ≤ 10^m/9 = 16^m-1(10/16)^m-1(10/9), which is < 16^m-1 ≤ n⁴ for m > 1. But the difference between any two numbers with digits 0 and 1 only has the digits 0, 1, 8 and 9.

31st IMO shortlist 1990