IMO 2017 Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

510 posts

#1 h Jul 18, 2017, 5:16 PM • 48 Y

Y by dagezjm, DrMath, claserken, MathSlayer4444, rightways, rafayaashary1, A_Math_Lover, GoJensenOrGoHome, anantmudgal09, laegolas, alphamom, brianapa, mira74, nmd27082001, kk108, jt314, Davi-8191, thepiercingarrow, Ultroid999OCPN, Mathuzb, Tawan, Lwande, integrated_JRC, Nelu2003, mathleticguyyy, Pluto1708, Purple_Planet, Lcz, fidgetboss_4000, itslumi, Pluto04, Hamroldt, HamstPan38825, centslordm, rama1728, megarnie, Quidditch, ImSh95, Rounak_iitr, sabkx, Lamboreghini, Adventure10, Mango247, deplasmanyollari, Sedro, dangerousliri, ItsBesi, cubres

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$ .

Proposed by Stephan Wagner, South Africa

This post has been edited 4 times. Last edited by djmathman, Jun 16, 2020, 4:13 AM
Reason: problem author

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cjquines0

510 posts

cjquines0

#2 h Jul 18, 2017, 5:16 PM • 6 Y

Y by MarkBcc168, megarnie, ImSh95, Adventure10, Mango247, cubres

First approximation based on this post.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathSlayer4444

1631 posts

MathSlayer4444

#3 h Jul 18, 2017, 5:18 PM • 7 Y

Y by Piazolla13, megarnie, ImSh95, Dhruv777, Adventure10, Mango247, cubres

It should be "for each integer," not "for an integer," I think.

(or maybe for every integer. Either way, it doesn't make much of a difference)

This post has been edited 1 time. Last edited by MathSlayer4444, Jul 18, 2017, 5:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

djmathman

7939 posts

djmathman

#4 h Jul 18, 2017, 5:22 PM • 7 Y

Y by HamstPan38825, megarnie, ImSh95, Jndd, Adventure10, Mango247, cubres

Sketch by 1=2 and i (which seems too simple????): if a0 is 0 mod 3, then bounding shows that you get 3 -> 6 -> 9 -> 3 ->...

If a0 is 2 mod 3, then you always increase by 3 and so its not periodic.
If a0 is 1 mod 3, then we also fail. Use strong induction. Base cases of a0 =1, a0=4 work. For IS, look at guys in the interval (m^2, (m+1)^2]. Youll eventually hit the upper bound of this sequence, and so next term is m+1, which is smaller than (m-1)^2 for large enough m.

This post has been edited 1 time. Last edited by djmathman, Jul 18, 2017, 5:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

WizardMath

2487 posts

WizardMath

#5 h Jul 18, 2017, 5:22 PM • 5 Y

Y by Mathlover1292, ImSh95, Adventure10, Mango247, cubres

Just plain bounding and cycles. Why is the problem so case bashy?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rafayaashary1

2541 posts

rafayaashary1

#6 h Jul 18, 2017, 5:23 PM • 4 Y

Y by PRMOisTheHardestExam, Adventure10, Mango247, cubres

Maybe I'm missing something, but: obviously $a_0\equiv 2\pmod{3}$ is a bust (it can't be periodic 'cause it adds and thus increases infinitely). If a term is not $2\pmod{3}$ , then it will eventually reach a perfect square in the "additive phase." Consider the case with $a_0\equiv 1\pmod{3}$ . From the above it suffices to consider the squares that are $1\pmod{3}$ . Indeed, it is fairly straightforward to show with some bounding that the structure is "downward directed" (a.k.a. essentially decreasing), and eventually funnels into $16\to4\to 2$ if they don't end up at the square of something that's $2\pmod{3}$ , which ends up adding infinitely from above. The $3\mid a_0$ case can be carried out similarly, but there are ~~some~~ solutions (obvious ones are $a_0\in\{3,6,9\}$ )

Edit: they should all funnel into the $3\to 6\to 9$ cycle for the same reasons as before.
Sniped

This post has been edited 2 times. Last edited by rafayaashary1, Jul 18, 2017, 5:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DrMath

2130 posts

DrMath

#7 h Jul 18, 2017, 5:25 PM • 3 Y

Y by Adventure10, Mango247, cubres

Idea: multiples of 3 work, you can show by strong induction you eventually hit either $3,6,9$ , which is gg.

2 mod 3 fails for obvious reasons.

1 mod 3 fails by strong induction - you have to hit a number that's 2 mod 3 eventually

also @above, technically it doesn't always funnel into 16 --> 4 --> 2, it could funnel into some other square that has the form $(3k+2)^2$ like 25 --> 5.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rafayaashary1

2541 posts

rafayaashary1

#8 h Jul 18, 2017, 5:28 PM • 4 Y

Y by Adventure10, Mango247, alexgsi, cubres

@above true, this is what happens when you only worry about the most pathological cases and forget the easier ones you threw away

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheTeaPot

19 posts

TheTeaPot

#15 h Jul 18, 2017, 6:09 PM • 2 Y

Y by Adventure10, cubres

1 mod 3 works for negatives

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

claserken

1772 posts

claserken

#16 h Jul 18, 2017, 6:16 PM • 14 Y

Y by alphamom, tarkus, mathematiculperson, PeppaBear, Tedi, Evenprime123, mathleticguyyy, ayan_mathematics_king, lahmacun, centslordm, Schur-Schwartz, Adventure10, Mango247, cubres

Just for completeness.
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

plagueis

157 posts

plagueis

#17 h Jul 18, 2017, 6:55 PM • 3 Y

Y by Adventure10, Mango247, cubres

It says $a_0>1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tintarn

9045 posts

Tintarn

#18 h Jul 18, 2017, 7:22 PM • 7 Y

Y by Sumgato, Safal_db, Adventure10, Mango247, RobertRogo, Sedro, cubres

The point why this problem is so remarkably easy seems to be the fact that, by checking the behaviour for small initial values (and what else are you going to do when confronted with such a problem?) you do not only see immediately what happens, but also pretty much why this happens. Converting these observations into a formal proof shouldn't be difficult for anyone who has seen the concept of mathematical induction (and, after all, any IMO contestant should belong to this group, right?).
I shall be very much surprised if this problem does not admit a conceivably higher average score compared to the first problems in recent IMOs.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

manuel153

324 posts

manuel153

#19 h Jul 18, 2017, 7:36 PM • 4 Y

Y by Submathematics, Toinfinity, Adventure10, cubres

@Tintarn:
Over the last few years, a lot of new countries has entered IMO. Many students of these countries have little or no training. I would guess that the intention of the jury was to offer a problem that is understandable (and solvable!) even for very un-experienced participants.
(As a side-effect, this might raise the bronze cut-off by one or two points.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tintarn

9045 posts

Tintarn

#20 h Jul 18, 2017, 7:41 PM • 10 Y

Y by manuel153, Safal_db, Toinfinity, Adventure10, Mango247, Sedro, RobertRogo, Math_DM, cubres, Gato_combinatorio

Oh sure. Note that I just tried to objectively explain what makes this problem so easy (in my eyes) and made a score prediction. I didn't (and didn't intend to) criticise this at all.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Gluncho

654 posts

Gluncho

#21 h Jul 18, 2017, 8:50 PM • 3 Y

Y by elecaii1981, Adventure10, cubres

Yh i think this problem is not imo level

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alba_tross1867

44 posts

alba_tross1867

#158 h Aug 5, 2024, 1:42 PM • 1 Y

Y by Hamzaachak

This problem holds so many cases, so I'd present shortly the main idea :
If $a_{0} \equiv 0 \pmod{3}$ : We can finish immediately by strong induction of multiples of $3$ and prove it works.
If $a_{0} \equiv 1 \pmod{3}$ : Again same idea to prove we'll definitely hit $a_{i} \equiv 2 \pmod{3}$ then the sequence will increasing forever
The remaining case is obvious.

This post has been edited 1 time. Last edited by alba_tross1867, Aug 5, 2024, 1:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

204 posts

de-Kirschbaum

#159 h Sep 2, 2024, 2:15 PM

Y by

We claim that the answer is all $a_0=3k$ .

It is obvious that $a_0 \equiv 2 \mod{3}$ doesn't work since no perfect squares are $2 \mod{3}$ , and every term in the sequence is $2 \mod{3}$ , which means the sequence will be monotonically increasing and thus no terms will appear infinitely many times.

Claim: All $3|a_0$ works. Since $x^2 \equiv 0 \mod{3} \implies x \equiv 0 \mod{3}$ , we know that all elements of the sequence are divisible by $3$ . Let us operate on the sequence until we must take square roots, then keep square rooting until we must take $+3$ as the next move. Call this number at $a_i=A=3t$ , where $3t$ is not a perfect square. We will keep incrementing $t$ by $1$ until $3t$ becomes a perfect square, then taking square root recovers $A$ . Thus $A$ appears infinitely many times.

Claim: All $a_0 \equiv 1 \mod{3}$ don't work. Note that $x^2 \equiv 1 \mod{3}$ could mean $x \equiv 1, 2\mod{3}$ , and if the modularity ever flips to $2 \mod{3}$ the sequence becomes monotonically increasing and we are done. So we just have to prove that eventually the modularity flips from $1$ to $2 \mod{3}$ .

Suppose a term $A$ does appear infinitely many times, that means the sequence should eventually be periodic. WLOG let $A=3k+1$ be the smallest element of the period. That means when we are at $a_i=3k+1$ , we should eventually reach $a_j=(3k+1)^2$ . However, note that $3k-1>0$ has $3k+1 \leq (3k-1)^2 < (3k+1)^2$ . Since $(3k-1)^2 \equiv 1 \mod{3}$ we will always hit it first, and then the next element becomes $3k-1 \equiv 2 \mod{3}$ so the sequence cannot be eventually periodic.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1329 posts

dolphinday

#160 h Sep 11, 2024, 7:05 PM

Y by

The answer is all $a_0$ so that $3 \mid a_0$ .
Say there is some $k$ so that $a_k = (3x)^2$ for $x > 1$ . Then $a_{k+1} = 3x$ . Notice that $3x - 3)^2 = 9x^2 - 18x + 9 > 3x$ for all $x > 1$ . Thus, $a_i$ will continuously keep on reaching smaller and smaller squares until $x = 3$ . From here, we get that $a_i$ goes in a loop; $3 - 6 - 9 - 3 - \dots$ , so for all $a_0$ there exists an $A$ .
Notice that $2$ is not a quadratic residue modulo $3$ so if at some point, $a_i$ becomes $2 \pmod{3}$ , there will be no such $A$ satisfying our requirements. Say that $a_0 \equiv 1\pmod{3}$ . Then, similarly, say that there is a $k$ so that $a_k = (3x + 1)^2$ . Notice that $(3x-2)^2 > 3x + 1$ for all $x > 1$ . However if $x = 1$ then $(3x - 2) = 1$ which is clearly not a valid number in the sequence. So it follows that $a_i$ must continously decrease until it reaches $4$ . Then, taking the square root of $4$ gets $2$ , which is $2\pmod{3}$ so there exists no such $A$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1327 posts

ezpotd

#161 h Sep 22, 2024, 12:44 AM

Y by

I claim the answer is only the numbers divisible by $3$ .

Proof nothing else works: Our aim will to be show the sequence eventually hits a number that is $2$ mod $3$ , at which point we are clearly done by quadratic residues (sequence just becomes adding $3$ ). Thus assume $a_0 \equiv 1 \mod 3$ . Construct zones of the form $((3n - 1)^2, (3n + 1)^2]$ . Clearly, if $a_i$ is not in such a zone, eventually we will have some $a_j = (3n + 2)^2$ , at which point we fail. Now we claim that if $a_i$ is always $1$ mod $3$ , it can never go up a zone and must eventually leave the zone by square root. The first part is trivial, we can never add $3$ to leave a zone since we will always just hit $(3n +1)^2$ . We are also eventually forced to hit $(3n +1)^2$ , at which point we go to $3n + 1$ . We see $3n +1 \le (3n - 1)^2$ is always true, so we always leave the zone. Since this process of going down zones can only occur a finite amount of times, we see that at some point we must end up not in a zone, at which point we are done.

Proof all multiples of $3$ work: Construct zones of the form $((3n)^2 , (3n + 3)^2 ]$ , we can clearly see that we can never leave a zone by adding $3$ , so we must always leave the zone by hitting a square root, and since $3n + 3 < 9n^2$ for all $n > 1$ , and all numbers are in zones, we must always hit the bottom zone, at which point we are stuck there forever.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SimplisticFormulas

131 posts

SimplisticFormulas

#162 h Nov 24, 2024, 8:20 AM • 1 Y

Y by radian_51

We claim that only $a_{0}= 3k, k \in \mathbb{Z}^{+}$ will work

CLAIM 1: If $3 \mid a_{0}$ , then $\{a_{i}\}_{i\ge 0}$ is eventually periodic:
PROOF: Note that $\{a_{i}\}_{i\ge 0}$ will remain constant modulo $3$ .
For any $3k$ achieved in the sequence, let $3(a-1)^2<k< 3a^2$ . Observe that after some time, $3(3a^2)$ is achieved, and the next value will be $3a<3k$ . Hence, the sequence will ultimately reach $3 \cdot 1=3$ , after which the sequence will become $3,6,9,3,6,9…$ .

CLAIM 2: If $1 <a_{0} \equiv 1 (\mod 3)$ , then $\{a_{i}\}_{i\ge 0}$ will eventually reach a number $m \equiv 2(\mod 3)$ , after which, the sequence is monotonically increasing.
PROOF: Let $r=k^2$ be the first perfect square in the sequence. Consider $a$ , the smallest positive integer not divisible by $3$ such that $k^2<a^4$ . Note that the next value in the sequence will be $k<a^2$ . Observe that $a^2$ is the smallest perfect square greater that $k$ not divisible by $3$ . Therefore, the sequence will again eventually reach $a^2$ , and therefore $a$ (since $a^2 \equiv 1 (\mod 3)$ ).
If $a \equiv 2(\mod 3)$ , then we are done. If not, then this process will keep occurring. At some point, it wil reach $4$ , which is the smallest integer $\equiv 1 (\mod 3)$ . After reaching $4$ , it will reach $2$ , and we are done.

Finally, note that if $a_{0} \equiv 2 (\mod 3)$ , then $\{a_{i}\}_{i\ge 0}$ is monotonically increasing since no square can leave a remainder of $2$ upon division by $3$ .

This post has been edited 1 time. Last edited by SimplisticFormulas, Nov 24, 2024, 2:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

577 posts

Maximilian113

#163 h Dec 18, 2024, 1:17 AM

Y by

Too simple?!?!?!

Clearly all $a_0 \equiv 0 \pmod 3$ work. Meanwhile, if $a_0 \equiv 2 \pmod 3$ the sequence will be strictly increasing as there are no perfect squares that are $2 \pmod 3.$

Now, we show by induction that $a_0 \equiv 1 \pmod 3$ doesn't work. The base cases, $a_0=1, 4, 7$ are trivial. Now, suppose that the proposition for $a_0 \leq 3k+1$ holds. Then for $a_0 = 3k+4,$ if the least perfect square congruent to $a_0$ is the same as that of $a_0-3,$ then we are done. Otherwise, if it is of the form $(3m+2)^2,$ we are clearly done. However, if it is of the form $(3m+1)^2,$ we are done too by the strong inductive hypothesis.

Therefore $a_0=3k$ is the only solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

639 posts

eg4334

#164 h Dec 23, 2024, 3:16 AM

Y by

The answer is only $\boxed{\text{multiples of 3}}$ . All $a_0 \equiv 2 \pmod{3}$ do not work because of quadratic residues and the resulting unbounded increase. All $a_0 \equiv 0 \pmod{3}$ clearly work as whenever we hit a perfect square the sequence decreases leading to a cycle. The main claim is that all $a_0 \equiv 1 \pmod{3}$ do not work which follows from strong induction. $a_0=4$ does not work by observation. If the next highest perfect square is of the form $(3n+2)^2, n \in \mathbb{Z}$ then the conclusion follows by the logic in the second sentence. Otherwise it is of the form $(3n+1)^2, n \in \mathbb{Z}$ which fails again from induction so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cubres

123 posts

cubres

#165 h Jan 1, 2025, 8:54 PM

Y by

Storage - grinding IMO probems

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#167 h Jan 4, 2025, 4:32 AM

Y by

wait why is this problem so bashy? my sol was just to case on a0 mod 3 (similar to e.g. post #4) and some bounding gives easy gg

Since all perfect squares are either $0$ or $1$ modulo $3$ , if we have $a_n\equiv2\pmod3$ for some index $n$ , then $a_0$ fails. Hence all $a_0$ satisfying $a_0\equiv2\pmod3$ fail.

We show that all $a_0$ with $a_0\equiv1\pmod3$ fail as well. By induction, suppose that all elements of $\{1,4,\dots,3k-2\}$ fail. If $3k-2$ is not a perfect square, then having $a_0=3k-2$ gives $a_1=3k+1$ , so having $a_0=3k+1$ will fail too. If $3k-2$ is a perfect square, having $a_0=3k+1$ will eventually yield some $a_j$ such that $a_j\le\sqrt{3k-2}+2<3k+1$ for $k>0$ and $a_0=3k+1$ will likewise fail by inductive hypothesis.

Note that $A=3$ works if $a_0\equiv0\pmod3$ . Indeed, all elements of our sequence will be divisible by $3$ . If $9b^2\le a_i<9(b+1)^2$ and $b>1$ for some $i$ , then $a_j=3(b+1)<9b^2\le a_i$ for some $j>i$ . Hence our sequence will continually exhibit smaller elements until $b=0$ , at which point it will cycle between $3$ , $6$ , and $9$ . $\blacksquare$

This post has been edited 1 time. Last edited by smileapple, Jan 4, 2025, 4:48 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

optimusprime154

28 posts

optimusprime154

#168 h Jan 8, 2025, 5:14 PM • 1 Y

Y by SorPEEK

if $a_0 \equiv 2 \pmod {3}$ then all $a_i \equiv 2 \pmod {3}$ so none of them can be a perfect square and it makes every one of them different.
if $a_0 \equiv 0 \pmod{3}$ then we can always find a number $k$ such that $n + 3k = 9t^2$ for some $t$ and thats when the cycle begins when the smallest number of that type is reached.
if $a_0 \equiv 1 \pmod {3}$ then we can always get to $2 \pmod{3}$ by that sequence and its quite easy to prove, this sequence fails for $1$ and $4$ then induction to finish

This post has been edited 2 times. Last edited by optimusprime154, Jan 8, 2025, 5:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Saucepan_man02

1365 posts

Saucepan_man02

#169 h Jan 17, 2025, 12:31 PM • 1 Y

Y by Sreepranad

If $a_0 \equiv 0 \pmod 3$ :

Note that, every term in the sequence is divisible by $3$ .
Let $m$ denote the minimum term in the sequence. If $m \ge 6$ , then: note that: $(m-3)^2 \ge m$ . Thus, there exists some $k$ such that: $(m-3)^2 \ge k^2 \ge m$ . Thus: we would have $k \le m-3 < m$ in the sequence, contradiction. Thus: $m=3$ and the sequence $3 \to 6 \to 9 \to 3 \cdots$ repeats.

If $a_0 \equiv 1 \pmod 3$ :

Let $m$ denote the minimum term in the sequence. If $m \equiv 2 \pmod 3$ , we are done as $2 \pmod 3$ is not a QR, which implies the sequence gets unbounded and increases monotonously (after some point). If $m \equiv 1 \pmod 3$ , then we have $m \ge 4$ . Then: $(m-2)^2 \ge m$ . Therefore, there exists some integer $k$ such that: $(m-2)^2 \ge k^2 \ge m$ . Therefore: $k \le m-2 < m$ exists in the sequence, which leads to contradiction. Thus we must have: $m \equiv 2 \pmod 3$ and we are done with no such value of $a_0$ .

If $a_0 \equiv 2 \pmod 3$ :

Evidently, $2 \pmod 3$ is not a QR, which implies the sequence gets unbounded and increases monotonously (after some point).

Thus, we are done with $3|a_0$ or any value of $a_0 = 3k$ works, where $k \in \mathbb N$ .

This post has been edited 1 time. Last edited by Saucepan_man02, Jan 17, 2025, 12:32 PM
Reason: EDIT

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

iStud

268 posts

iStud

#170 h Jan 28, 2025, 12:55 PM

Y by

didn't expected to use strong induction on this problem :-D

Note that $k^2\equiv 0,1\pmod{3}$ for all $k\in\mathbb{N}$ . If $a_0\equiv 2\pmod{3}$ , then the sequence becomes $a_0,a_0+3,a_0+6,\dots$ and eventually $\{a_n\}$ will be an unbounded sequence, which doesn't meet the problem desire. If $a_0\equiv 0\pmod{3}$ , we divide into two cases. First case when $a_0$ is a quadratic number clearly works since $\{a_n\}$ is literally bounded by $a_0$ , so by doing infinite terms of the sequence, we'll eventually ended up having a number $A$ such that $a_n=A$ for infinitely many values of $n$ . Now if $a_0$ isn't a quadratic form, then we can assure that we will have a quadratic number $a_p=a_0+3p$ for some $p\in\mathbb{N}$ , so we're done by using the similar argument as the previous case.

Now we come up with the case when $a_0\equiv 1\pmod{3}$ . The idea is quite simple; we use strong induction. Base case when $a_0=4$ (quadratic) and $a_0=7$ (not quadratic) are done just by checking them. Assume that for the induction hypothesis, we have $a_0=k$ doesn't works for some $k\in\mathbb{N}$ . Note that we can have $k$ and $k+3$ are both quadratic numbers iff $k=1$ , which clearly opposing the problem condition ( $a_0>1$ ). So we'll basically divide into three cases from now on. If none of $k$ and $k+3$ are quadratic numbers, then we're done by our induction hypothesis. The similar argument applies for when $k+3$ is a quadratic number. Now for the case when $k$ is quadratic, let $k=t^2$ for some $t\in\mathbb{N}$ . Then the sequence becomes $t^2,t,\dots$ . Now we have $\{a_n\}$ is bounded by $k=t^2$ , so by noticing that $t<t^2=k$ (since $t^2=k\ne 1$ and $t\in\mathbb{N}$ ) we're done by the induction hypothesis.

Overall, all $a_0$ such that $3\mid a_0$ work as solutions. $\blacksquare$

This post has been edited 1 time. Last edited by iStud, Apr 3, 2025, 4:35 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

183 posts

lelouchvigeo

#171 h Jan 30, 2025, 6:35 PM • 1 Y

Y by alexanderhamilton124

Easy headsolve

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

363 posts

blueprimes

#172 h Apr 3, 2025, 1:33 AM

Y by

The answer is all $3 \mid a_0$ .

To prove these work, we strong induct on $a_0$ . Note that the cases $a_0 = 3, 6, 9,$ all eventually cycle $3, 6, 9,$ which works, now assume the claim holds for $a_0 \le 3m$ for some integer $m \ge 3$ . When $a_0 = 3m + 3$ , the sequence eventually generates a term $3k$ where $k \in \mathbb{Z}_{\ge 0}$ such that $(3k - 3)^2 < 3m + 3 \le (3k)^2$ . So
$3k \le (3k - 3)^2 \iff 3k^2 - 7k + 3 \ge 0$ which is true since $k \ge 2$ . Thus $3k < 3m + 3$ so our induction is complete.

Now we show everything else fails, clearly if $a_0 \equiv 2 \pmod{3}$ no perfect square emerges so the sequence diverges. On the other hand, if $a_0 \equiv 1 \pmod{3}$ , assume that the sequence works. Then we can never have a $2 \pmod{3}$ term by above, we will strong induct to show that such a sequence cannot exist.

Note that the cases $a_0 = 4, 7, 10, 13, 16$ eventually yields $4, 2, \dots,$ which diverges. Now assume the sequence eventually diverges for $a_0 \le 3m + 1$ for an integer $m \ge 6$ . Let $a_0 = 3m + 4$ , then at some point we generate the term $3k + 1$ where $(3k - 2)^2 < 3m + 4 \le (3k + 1)^2$ but
$3k + 1 \le (3k - 2)^2 \iff 3k^2 - 5k + 1 \ge 0$ which holds since $k \ge 2$ . So $3k + 1 < 3m + 4$ and the induction is complete.

Voilà.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ND_

60 posts

ND_

#173 h Tuesday at 10:36 AM

Y by

Answer: $3 \mid a_0$

Case 1: $a_0 \equiv 2$ : The sequence is obviously increasing as $\sqrt {a_n}$ is never a square.
Case 2: $a_0 \equiv 0$ : By PHP, some term must occur infinitely many times as the sequence can only take the multiples of 3 in $\left[3, 9 \left ( \left \lceil \sqrt {\frac{a_n}{9}} \right \rceil \right )^2\right]$
Case 3: $a_0 \equiv 1$ : ${a}$ can only take values in Case 1, or smaller values in this case, none of which work by induction on $a_0$ .

Z K Y