IMO 1983 SL 14

Origin: POL

Problem

Prove or disprove: From the interval [1, . . . , 30000] one can select a set of 1000 integers containing no arithmetic triple (three consecutive numbers of an arithmetic progression).

Solution

Let Tn be the set of all nonnegative integers whose ternary representations consist of at most n digits and do not contain a digit 2. The cardinality of Tn is 2n, and the greatest integer in Tn is 11 . . . 1 = 30 + 31 +\cdot \cdot \cdot+ 3n−1 = (3n −1)/2. We claim that there is no arithmetic triple in Tn. To see this, suppose x, y, z \inTn and 2y = x + z. Then 2y has only 0’s and 2’s in its ternary representation, and a number of this form can be the sum of two integers x, z \inTn in only one way, namely x = z = y. But |T10| = 210 = 1024 and max T10 = (310 −1)/2 = 29524 < 30000. Thus the answer is yes.