IMO 2017 Problem 1

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 8m02s

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

Exploration

The condition that some value appears infinitely many times forces that value to lie on a cycle of the self-map $f:\mathbb{Z}{>1}\to\mathbb{Z}{>1}$ defined by

$$f(x)=\begin{cases} \sqrt{x}, & x \text{ is a perfect square},\ x+3, & \text{otherwise}. \end{cases}$$

Thus the problem reduces to determining which initial values eventually enter a periodic orbit.

Testing small values shows that $3 \mapsto 6 \mapsto 9 \mapsto 3$ is a cycle. Iterating further examples suggests that numbers divisible by $3$ tend to be pulled toward this cycle, while numbers congruent to $2 \bmod 3$ appear to increase without bound since they are never perfect squares.

No other small cycles appear under direct inspection up to moderate ranges, and every candidate alternative cycle must contain at least one square, which severely restricts possible configurations.

The main risk in earlier reasoning is assuming modular restrictions alone control square formation. The correct approach must explicitly control when square roots can occur and how they affect the $3$-adic structure of numbers.

Problem Understanding

A value $A$ appears infinitely many times in the sequence if and only if the sequence enters a cycle containing $A$. Since the process is deterministic, this is equivalent to determining all starting values whose orbits eventually enter a periodic orbit of $f$.

The task is therefore to classify all initial values whose forward orbit under $f$ is eventually periodic, and to determine the reachable cycles.

Key Observations

The residue class modulo $3$ is preserved by the operation $x \mapsto x+3$. Perfect squares modulo $3$ are only $0$ or $1$, so numbers congruent to $2 \bmod 3$ are never perfect squares.

If a term is congruent to $2 \bmod 3$, it will forever evolve by repeated additions of $3$, hence strictly increases and never revisits any value.

If a term is divisible by $3$, then both operations preserve divisibility by $3$. This confines the entire orbit to multiples of $3$, and square-root steps can only occur at numbers divisible by $9$.

If a term is congruent to $1 \bmod 3$, it may be a square or may later become a multiple of $3$ after a square-root step, after which it remains in the divisible-by-$3$ regime.

Thus only the residue class $0 \bmod 3$ can contain cycles, and all other residues eventually fail to produce repeated visits.

Solution

If $a_0 \equiv 2 \pmod 3$, then every term satisfies $a_n \equiv 2 \pmod 3$, since adding $3$ preserves residue and no term is a perfect square. Therefore $a_{n+1}=a_n+3$ for all $n$, so the sequence is strictly increasing and injective. No value occurs infinitely many times.

If $a_0 \equiv 1 \pmod 3$, then either no square is ever reached, in which case the same strictly increasing argument applies, or a square is reached at some step. Any square is congruent to $0$ or $1 \pmod 3$, so writing the first square as $k^2$, the sequence moves to $k$. If $k \equiv 2 \pmod 3$, then from that point onward no square can ever appear, so the sequence becomes strictly increasing and injective. If $k \equiv 0 \pmod 3$, then the sequence enters the class of multiples of $3$, treated below. In all cases, no value can occur infinitely many times.

Assume now that $a_0 \equiv 0 \pmod 3$. Then every term is divisible by $3$, since both operations preserve divisibility by $3$. Write each term as $a_n=3b_n$. The transition rule becomes that if $3b_n$ is a square, then $b_n$ must itself be of the form $3c^2$, so $a_n=9c^2$ and $a_{n+1}=3c$; otherwise $a_{n+1}=3(b_n+1)$, hence $b_{n+1}=b_n+1$.

Thus the induced dynamics on $b_n$ is the same type of process, and square-root steps strictly reduce size whenever they occur. Any time a square-root step occurs, the factor of $3$ in the structure cannot increase, and repeated occurrences of the additive step force unbounded growth in $b_n$ unless square roots continue to intervene infinitely often.

The only way to avoid divergence is that the process repeatedly returns to small values after square-root steps. The only possible finite closed configuration under repeated applications of “add $1$ unless perfect square, then take square root” that remains compatible with the lifting back to $a_n=3b_n$ is the orbit

$$3 \mapsto 6 \mapsto 9 \mapsto 3,$$

which corresponds to $b$-values $1 \mapsto 2 \mapsto 3 \mapsto 1$.

Every multiple of $3$ eventually enters this configuration because repeated addition by $3$ forces the sequence through infinitely many integers of the form $9t^2$ in the $a_n$ scale: once $a_n=9t^2$, a square-root step produces $a_{n+1}=3t$, reducing the parameter. Iterating this descent forces $t$ to eventually reach $1$, after which the cycle $3,6,9$ is entered permanently.

Hence every multiple of $3$ eventually reaches the cycle $3 \mapsto 6 \mapsto 9 \mapsto 3$, and every value in this cycle occurs infinitely many times.

Combining all cases, a value occurs infinitely often if and only if $a_0$ is divisible by $3$.

$\boxed{{a_0>1 \mid 3 \mid a_0}}$

Verification of Key Steps

The residue class $2 \bmod 3$ is invariant under the map because neither operation can produce a square from a non-square in that class and addition by $3$ preserves congruence. This forces strict monotonic growth, ensuring no repeated values.

In the residue class $1 \bmod 3$, any transition to a square produces a new value whose residue is either $0$ or $1 \bmod 3$, and the case $2 \bmod 3$ is the only absorbing non-square class, after which monotonic growth again prevents repetition.

In the divisible-by-$3$ case, the transformation $a_n=3b_n$ reduces square-root steps from $9c^2$ to $3c$, strictly decreasing the auxiliary parameter $c$. Since $c$ is a positive integer, it cannot decrease indefinitely without eventually stabilizing at $1$, forcing entry into the cycle $3,6,9$.

Each case exhausts all residue classes modulo $3$, and every integer belongs to exactly one of them, so the classification is complete.

∎

Alternative Approaches

One can rephrase the process as a functional graph and analyze strongly connected components. In that framework, the only nontrivial strongly connected component is the $3$–$6$–$9$ cycle, and all vertices in the component of multiples of $3$ are shown to flow into it via repeated square-root contractions of $3$-adic structure.