Romanian Mathematical Olympiad - Final Round

As for $x \in \{0, 1, \dots, 2^n - 1\}$ we have $f(x) \in \{0, 1, \dots, 2^n - 1\}$, and for $x \ge 2^n$ we have $f(x) < x$, we get $f(x) \le \max(x, 2^n - 1)$. It follows that if $x \in A$, then
$$x = f^{[n]}(x) \le \max(f^{[n-1]}(x), 2^n - 1) \le \dots \le \max(f(x), 2^n - 1).$$
If $x \ge 2^n$, then $x \le f(x)$, a contradiction, thus $A$ is contained in $\{0, 1, \dots, 2^n - 1\}$.

We shall prove the equality $A = \{0, 1, \dots, 2^n - 1\}$. We give two proofs for the reverse inclusion.

i.
From $f(2^n - 1) = 2^n - 1$ deduce $2^n - 1 \in A$. As $2f(x) \in \{x, x+2^n-1\}$, $2f(x)$ is congruent to $x$ modulo $2^n - 1$. Inductively, $x \equiv 2^n f^{[n]}(x) \equiv f(x) \pmod{2^n - 1}$. Because $f(x) < 2^n - 1$ for $x < 2^n - 1$, we obtain $f^{[n]}(x) = x$ if $x \in \{0, 1, \dots, 2^n - 2\}$.

ii.
Use base 2 to represent any number in $x \in \{0, 1, \dots, 2^n - 1\}$ using $n$ digits, putting zero at the beginning, if necessary. To obtain $f(x)$ from $x$ one has to move the last digit of $x$ on the first position. After $n$ movements the digits of $x$ are at the same places as at the beginning, that is $f^{[n]}(x) = x$.