1983 IMO Problems/Problem 5
Is it possible to choose distinct positive integers, all less than or equal to , no three of which are consecutive terms of an arithmetic progression? Justify your answer.
The answer is yes. We will construct a sequence of integers that satisfies the requirements.
Take the following definition of : in base 3 has the same digits as in base 2. For example, since , .
First, we will prove that no three 's are in an arithmetic progression. Assume for sake of contradiction, that are numbers such that . Consider the base 3 representations of both sides of the equation. Since consists of just 0's and 1's in base three, consists of just 0's and 2's base 3. No whenever has a 0, both and must have a 0, since both could only have a 0 or 1 in that place. Similarly, whenever has a 2, both and must have a 1 in that place. This means that , which is a contradiction.
Now since , . Hence, the set is a set of 1983 integers less than with no three in arithmetic progression.