USA IMO

We prove that the range of $f$ is the set $T$ of rational numbers of the form $m/2^n$ for $m \in \mathbb{Z}$ and $n \in \mathbb{N}_0^+$ (also known as the dyadic rational numbers). For $x, y \in T$, we write $x \equiv y \pmod 3$ to mean that the numerator of $x - y$, when written in lowest terms, is divisible by 3. Define the function $g : T \to \{0, 1, 2\}$ by declaring that for $x \in T$, $g(x)$ is the unique element of $\{0, 1, 2\}$ such that $g(x) \equiv x \pmod 3$.

We first check that $f$ is one-to-one. Suppose that $f(a) = f(b)$ for some $a, b \in \mathbb{N}_0^+$ with $a < b$; choose such a pair with $b$ minimal. Now note that $f(a) \equiv a \pmod 3$ and $f(b) \equiv b \pmod 3$ from the definition of $f$. Hence $a \equiv b \pmod 3$. Choose the $i \in \{0, 1, 2\}$ that is congruent to $a$ and $b$ modulo 3, and put $a' = (a-i)/3$ and $b' = (b-i)/3$. Then $f(a') = f(b')$, but $a' < b'$ and $b' < b$ since $b > 0$. This contradicts the choice of $a$ and $b$. Hence no such pairs exist.

We next verify that $T$, which clearly contains the range of $f$, is in fact equal to it. Define the map $h : T \to T$ by setting $h(x) = \frac{2}{3}(g(x)-x)$. Then $x$ is in the image of $f$ whenever $h(x)$ is: if $h(x) = f(a)$, then $x = f(3a + g(x))$. Hence it suffices to show that if one starts from $x$ and applies $h$ repeatedly, one eventually ends up with an element of the range of $f$.

First note that if $x$ is not an integer, then $g(x) - x$ has the same denominator as $x$, and $h(x)$ has denominator half of that. Hence some $x_i$ is an integer.

Next, by the Triangle Inequality,
$$|h(x)| \leq \frac{2}{3}(2 + |x|) < |x|$$
whenever $|x| > 4$. Thus, our process eventually hits an integer of absolute value bounded by 4. Simple computation yields the following table:

¿From the table, it is clear that starting from any point in $\{-4, -3, \ldots, 4\}$, within 4 applications of $h$, our process hits zero. Since $f(0) = 0$, this value is in the range of $f$, so we are done.