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 \left\lfloor \frac{2b_k}{n} \right\rfloor - n \left\lfloor \frac{b_k}{n} \right\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} \pmod{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} \pmod{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$.

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 \iff \{x\} = 0 \text{ and } f(x) = \frac{1}{2} \iff \{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}) = \dots = 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}}, \quad 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$.