1983 IMO Problems/Problem 5
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.
Solution
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.
See Also
1983 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |