# Difference between revisions of "1983 IMO Problems/Problem 5"

m (→Solution) |
Umtympswede (talk | contribs) (→Solution) |
||

Line 3: | Line 3: | ||

==Solution== | ==Solution== | ||

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

+ | |||

+ | Take the following definition of <math> a_n </math>, <math> a_n </math> in base 3 has the same digits as <math> n </math> in base 2. For example, since <math> 6=110_2 </math>, <math>a_n=110_3=12</math>. | ||

+ | |||

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

+ | |||

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

## Revision as of 11:08, 15 May 2020

## 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 with no three in arithmetic progression.