Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Created page with "==Problem 5== Is it possible to choose <math>1983</math> distinct positive integers, all less than or equal to <math>10^5</math>, no three of which are consecutive terms of an...")
 
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
==Problem 5==
 
==Problem 5==
 
Is it possible to choose <math>1983</math> distinct positive integers, all less than or equal to <math>10^5</math>, no three of which are consecutive terms of an arithmetic progression? Justify your answer.
 
Is it possible to choose <math>1983</math> distinct positive integers, all less than or equal to <math>10^5</math>, 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 <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.
 +
 +
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.
 +
 +
== See Also == {{IMO box|year=1983|num-b=4|num-a=6}}

Latest revision as of 22:40, 29 January 2021

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.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1983_IMO_Problems/Problem_5&oldid=144011"