Difference between revisions of "1983 IMO Problems/Problem 5"
Umtympswede (talk | contribs) (→Solution) |
Umtympswede (talk | contribs) 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> | + | 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 10:12, 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 less than with no three in arithmetic progression.
