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 "2017 IMO Problems/Problem 1"
(→‎Solution)
 
(13 intermediate revisions by the same user not shown)
Line 10: Line 10:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
 
 +
First we observe the following:
 +
 
 +
When we start with <math>a_0=3</math>, we get <math>a_1=6</math>, <math>a_2=9</math>, <math>a_3=3</math> and the pattern <math>3,6,9</math> repeats.
 +
 
 +
When we start with <math>a_0=6</math>, we get <math>a_1=9</math>, <math>a_2=3</math>, <math>a_3=6</math> and the pattern <math>3,6,9</math> repeats.
 +
 
 +
When we start with <math>a_0=9</math>, we get <math>a_1=3</math>, <math>a_2=6</math>, <math>a_3=9</math> and the pattern <math>3,6,9</math> repeats.
 +
 
 +
When we start with <math>a_0=12</math>, we get <math>a_1=15</math>, <math>a_2=15</math>,..., <math>a_8=36</math>, <math>a_9=6</math>, <math>a_{10}=9</math>, <math>a_{11}=3</math> and the pattern <math>3,6,9</math> repeats.
 +
 
 +
When this pattern <math>3,6,9</math> repeats, this means that there exists a number <math>A</math> such that <math>a_n = A</math> for infinitely many values of <math>n</math> and that number <math>A</math> is either <math>3,6,</math> or <math>9</math>.
 +
 
 +
When we start with any number <math>a_0\not\equiv 0\; mod\; 3</math>, we don't see a repeating pattern.
 +
 
 +
Therefore the claim is that <math>a_0=3k</math> where <math>k</math> is a positive integer and we need to prove this claim.
 +
 
 +
When we start with <math>a_0=3k</math>, the next term if it is not a square is <math>3k+3</math>, then <math>3k+6</math> and so on until we get <math>3k+3p</math> where <math>p</math> is an integer and <math>(k+p)=3q^2</math> where <math>q</math> is an integer.  Then the next term will be <math>\sqrt{9q^2}=3q</math> and the pattern repeats again when <math>q=k</math> or when <math>q=3</math> or <math>6</math>.
 +
 
 +
In order for these patterns to repeat, any square in the sequence need to be a multiple of 3. 
 +
 
 +
To try the other two cases where <math>a_0\not\equiv 0\; mod\; 3</math>, we can try <math>a_0=3k\pm 1</math> then the next terms will be in the form  <math>3k+3p\pm 1 = 3(k+p) \pm 1</math>.
 +
 
 +
When <math>3(k+p) \pm 1</math> is a square, it will not be a multiple of <math>3</math> because <math>3(k+p) \pm 1</math> is not a multiple of <math>3</math> and <math>3(k+p) \pm 1 \ne 9q^2</math> because <math>3(k+p) \pm 1 \equiv \pm 1\; mod\; 3</math> and <math>q^2</math> would have to be <math>\frac{(k+p)}{3} \pm \frac{1}{9}</math> which is not an integer even if <math>k+p</math> is a multiple of <math>3</math>.
 +
 
 +
Therefore the pattern doesn't repeat for any of the other cases where <math>a_0=3k\pm 1</math> and only repeats when <math>a_0\equiv 0\; mod\; 3</math>
 +
 
 +
So, the answer to this problem is <math>a_0=3k\;\forall k \in \mathbb{Z}^{+}</math> and <math>A=3,6,</math> or <math>9</math>.
 +
 
 +
~Tomas Diaz. orders@tomasdiaz.com
 +
 
 +
{{alternate solutions}}
  
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=2017|before=First Problem|num-a=2}}
 
{{IMO box|year=2017|before=First Problem|num-a=2}}

Latest revision as of 02:04, 19 November 2023

Problem

For each integer $a_0 > 1$, define the sequence $a_0, a_1, a_2, \ldots$ for $n \geq 0$ as \[a_{n+1} = \begin{cases} \sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\ a_n + 3 & \text{otherwise.} \end{cases}\]Determine all values of $a_0$ such that there exists a number $A$ such that $a_n = A$ for infinitely many values of $n$.

Solution

First we observe the following:

When we start with $a_0=3$, we get $a_1=6$, $a_2=9$, $a_3=3$ and the pattern $3,6,9$ repeats.

When we start with $a_0=6$, we get $a_1=9$, $a_2=3$, $a_3=6$ and the pattern $3,6,9$ repeats.

When we start with $a_0=9$, we get $a_1=3$, $a_2=6$, $a_3=9$ and the pattern $3,6,9$ repeats.

When we start with $a_0=12$, we get $a_1=15$, $a_2=15$,..., $a_8=36$, $a_9=6$, $a_{10}=9$, $a_{11}=3$ and the pattern $3,6,9$ repeats.

When this pattern $3,6,9$ repeats, this means that there exists a number $A$ such that $a_n = A$ for infinitely many values of $n$ and that number $A$ is either $3,6,$ or $9$.

When we start with any number $a_0\not\equiv 0\; mod\; 3$, we don't see a repeating pattern.

Therefore the claim is that $a_0=3k$ where $k$ is a positive integer and we need to prove this claim.

When we start with $a_0=3k$, the next term if it is not a square is $3k+3$, then $3k+6$ and so on until we get $3k+3p$ where $p$ is an integer and $(k+p)=3q^2$ where $q$ is an integer. Then the next term will be $\sqrt{9q^2}=3q$ and the pattern repeats again when $q=k$ or when $q=3$ or $6$.

In order for these patterns to repeat, any square in the sequence need to be a multiple of 3.

To try the other two cases where $a_0\not\equiv 0\; mod\; 3$, we can try $a_0=3k\pm 1$ then the next terms will be in the form $3k+3p\pm 1 = 3(k+p) \pm 1$.

When $3(k+p) \pm 1$ is a square, it will not be a multiple of $3$ because $3(k+p) \pm 1$ is not a multiple of $3$ and $3(k+p) \pm 1 \ne 9q^2$ because $3(k+p) \pm 1 \equiv \pm 1\; mod\; 3$ and $q^2$ would have to be $\frac{(k+p)}{3} \pm \frac{1}{9}$ which is not an integer even if $k+p$ is a multiple of $3$.

Therefore the pattern doesn't repeat for any of the other cases where $a_0=3k\pm 1$ and only repeats when $a_0\equiv 0\; mod\; 3$

So, the answer to this problem is $a_0=3k\;\forall k \in \mathbb{Z}^{+}$ and $A=3,6,$ or $9$.

~Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2017 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_IMO_Problems/Problem_1&oldid=204624"