1983 IMO Problems/Problem 5

Problem 5

Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$ , no three of which are consecutive terms of an arithmetic progression? Justify your answer.

Solution

The answer is yes. We will construct a sequence of integers that satisfies the requirements.

Take the following definition of $a_n$ : $a_n$ in base 3 has the same digits as $n$ in base 2. For example, since $6=110_2$ , $a_6=110_3=12$ .

First, we will prove that no three $a_n$ 's are in an arithmetic progression. Assume for sake of contradiction, that $i < j < k$ are numbers such that $2a_j=a_i + a_k$ . Consider the base 3 representations of both sides of the equation. Since $a_j$ consists of just 0's and 1's in base three, $2a_j$ consists of just 0's and 2's base 3. No whenever $2a_j$ has a 0, both $a_i$ and $a_k$ must have a 0, since both could only have a 0 or 1 in that place. Similarly, whenever $2a_j$ has a 2, both $a_i$ and $a_k$ must have a 1 in that place. This means that $a_i=a_k$ , which is a contradiction.

Now since $1983=11110111111_2$ , $a_{1983} = 11110111111_3 < \frac{3^{11}}{2} < 10^5$ . Hence, the set $\{a_1,a_2,...a_{1983}\}$ is a set of 1983 integers less than $10^5$ with no three in arithmetic progression.

Page

Toolbox

Search

1983 IMO Problems/Problem 5

Problem 5

Solution