IMO 1975 SL 5

Let M be the set of all positive integers that do not contain the

imoshortlistmathematicsolympiad

IMO 1975 SL 5

Origin: SWE

Problem

Let M be the set of all positive integers that do not contain the digit 9 (base 10). If x1, . . . , xn are arbitrary but distinct elements in M, prove that n  j=1 xj < 80.

Solution

There are exactly 8 \cdot 9k−1 k-digit numbers in M (the first digit can be chosen in 8 ways, while any other position admits 9 possibilities). The least of them is 10k, and hence  xj<10k xj

k  i=1  10i−1\leqxj<10i xj < k  i=1  10i−1\leqxj<10i 10i−1

k  i=1 8 \cdot 9i−1 10i−1 = 80  1 −9k 10k  < 80.