IMO Team Selection Team Selection Test

We prove the following stronger statement: For any $k \ge 0$ and $a \ge 1$, the values $f(a), f(a+1), \dots, f(a+3^k - 1)$ are all distinct modulo $3^k$; that is, these numbers form a complete set of residues modulo $3^k$. We will induct on $k$, the case $k=0$ being trivial.

Assume the statement true for a given $k$; we will prove it for $k+1$. For any $a \ge 1$, we have
$$\begin{aligned} & f(a + 3^k) - f(a) \\ &= [f(a+1) - f(a)] + [f(a+2) - f(a+1)] + \dots + [f(a + 3^k) - f(a + 3^k - 1)] \\ &= 2^{f(a)} + 2^{f(a+1)} + \dots + 2^{f(a+3^k-1)}. \end{aligned}$$

Note that by Euler's theorem, to know $2^x$ modulo $3^{k+1}$ ($x \ge 1$), it suffices to know $x$ modulo $\varphi(3^{k+1}) = 2 \cdot 3^k$. Now $f(x)$ is always odd (this follows from the definition), while the inductive hypothesis tells us that $f(a), \dots, f(a+3^k-1)$ are distinct mod $3^k$. Hence sets
$$\{f(a), \dots, f(a + 3^k - 1)\} \quad \text{and} \quad \{1, 3, 5, \dots, 2 \cdot 3^k - 1\}$$
are congruent to each other modulo $2 \cdot 3^k$. Therefore, modulo $3^{k+1}$, we have
$$f(a + 3^k) - f(a) \equiv 2^1 + 2^3 + 2^5 + \dots + 2^{2 \cdot 3^k - 1} \equiv 2(1 + 4 + 4^2 + \dots + 4^{3^k - 1}) \equiv \frac{2(4^{3^k} - 1)}{3}.$$
By the binomial theorem, we have
$$4^{3^k} - 1 = (1 + 3)^{3^k} - 1 = 3 \cdot \binom{3^k}{1} + \dots,$$
where each of the remaining summands are divisible by $3^{k+2}$; hence
$$f(a + 3^k) - f(a) \equiv 2 \cdot 3^k \pmod{3^k} \qquad (20)$$
for all $a$.

Returning to the sequence
$$f(a), f(a+1), \dots, f(a + 3^{k+1} - 1),$$
we see that, since $f(b) \equiv f(b + 3^k)$ modulo $3^k$ (a consequence of the inductive hypothesis), the terms congruent to one another modulo $3^k$ come in triples $(f(b), f(b + 3^k), f(b + 2 \cdot 3^k))$. By (20), these terms, modulo $3^{k+1}$, are congruent to $(f(b), f(b) + 2 \cdot 3^k, f(b) + 3^k)$, which are pairwise distinct, completing our induction.