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

(Solution)
m (Solution)
Line 5: Line 5:
 
The answer is yes. We will construct a sequence of integers that satisfies the requirements.
 
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>.
+
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_6=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.
 
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.
+
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 less than <math> 10^5 </math> with no three in arithmetic progression.

Revision as of 11:12, 15 May 2020

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.