Final Round of the 73rd Czech and Slovak Mathematical Olympiad (March 17–20, 2024)

Let $f$ be the function $f(x)=3x-\lfloor 2x\rfloor -\lfloor x\rfloor$, then the defining relation can be conveniently written as $a_{k+1}=f(a_k)$.

Note that since $f(0)=f(1)=0$ and $f(\frac{1}{2})=\frac{1}{2}$, the sequence will be eventually constant whenever $\frac{1}{2}$ or $1$ occurs in it. We can also observe that $f(x)=3x$ for $0<x<\frac{1}{2}$. Therefore, by a simple inductive argument, we can show that for any non-negative integer $\alpha$ and $n=3^{\alpha }$, we have $a_{\alpha +1}=1$ and, similarly, for $n=2\cdot 3^{\alpha }$, we have $a_{\alpha +1}=\frac{1}{2}$. Therefore, the integers $n$ of this form are solutions.

Now, we will show that there are no other solutions. In order to do that, it suffices to prove that for any $n$ satisfying the hypothesis of the problem, there must exist some non-negative integer $\alpha$ such that $n\mid 2\cdot 3^{\alpha }$.

So, suppose that the sequence is eventually constant for some value of $n$. Then we can define an auxiliary sequence $(b_k)$ given by $b_k=n{a}_k$, then this new sequence is given by a recurrence relation $b_1=1$ and $$b_{k+1}=3b_k-n\lfloor \frac{2b_k}{n}\rfloor -n\lfloor \frac{b_k}{n}\rfloor .$$ By a simple induction, we can see that $b_k$ is a non-negative integer and moreover that $b_k\equiv 3^{k-1}(\mathrm{mod}n)$ for all $k\ge 1$.

Since the sequence is eventually constant, there exists some $\alpha \ge 0$ with $b_{\alpha +2}=b_{\alpha +1}$, so the congruence that we have derived above gives $3^{\alpha +1}\equiv 3^{\alpha }(\mathrm{mod}n)$, which is clearly equivalent to the desired statement $n\mid 2\cdot 3^{\alpha }$, so we are done.

Conclusion. The sequence is eventually constant if and only if $n$ is of the form $3^{\alpha }$ or $2\cdot 3^{\alpha }$ for some non-negative integer $\alpha$.

---

Alternative solution.

It is possible to find all values $a_1\in \mathbb{R}$ for which the sequence is eventually constant. As before, let $f(x)=3x-\lfloor 2x\rfloor -\lfloor x\rfloor$. If we denote the fractional part of a real number $t$ as $\{t\}$, then we have $$f(x)=3x-\lfloor 2x\rfloor -\lfloor x\rfloor =(2x-\lfloor 2x\rfloor )+(x-\lfloor x\rfloor )=\{2x\}+\{x\}.$$ From this expression, it is clear that the function $f$ is 1-periodic, hence we get: $$f(f(x))=f(\{2x\}+\{x\})=f(\{2x\}+\{x\}+\lfloor 2x\rfloor -\lfloor x\rfloor )=f(3x).$$ We can also use this expression for $f$ to prove that the fixed points of $f$ are precisely $0$ and $\frac{1}{2}$ (in the first solution, we didn't need the fact that these are all the fixed points). Moreover, we can show that $$f(x)=0⟺\{x\}=0\text{ and }f(x)=\frac{1}{2}⟺\{x\}=\frac{1}{2}\text{ or }\{x\}=\frac{1}{6}.$$ Finally, suppose that the sequence is eventually constant for a given value of $a_1$. Then $f(a_{k+1})=a_{k+1}$ for some positive integer $k$, hence $a_{k+1}=0$ or $a_{k+1}=\frac{1}{2}$. By a simple inductive argument, we see that $$a_{k+1}=f(a_k)=f(f(a_{k-1}))=f(3a_{k-1})=\cdots =f(3^{k-1}{a}_1),$$ so by the equivalences that we've stated above, this happens if and only if $\{3^{k-1}{a}_1\}\in \{0,\frac{1}{6},\frac{1}{2}\}$.

Therefore, we have shown that the sequence stabilizes after at most $k+1$ steps if and only if $a_1$ is of the form $$a_1=\frac{m}{3^{k-1}},a_1=\frac{6m+1}{2\cdot 3^k}\text{ or }{a}_1=\frac{2m+1}{2\cdot 3^{k-1}},$$ where $k\ge 1$ and $m$ is an integer. One can also simplify the answer by noting that the third case is contained inside the second one.

Conclusion. The sequence is eventually constant if and only if $a_1=\frac{m}{3^k}$ or $a_1=\frac{6m+1}{2\cdot 3^k}$ for some non-negative integer $k$ and an integer $m$.