USA TST Selection Test for 67th IMO and 15th EGMO

The answer is $\{a\}$, $\{a, a+1\}$, $\{a, a+1, a+2, \dots\}$, and $\mathbb{Z}$, for arbitrary $a \in \mathbb{Z}$. For constructions, it is not hard to show that if $g: \mathbb{R} \to \mathbb{R}$ is a convex function, then $\lfloor g \rfloor$ satisfies the functional equation. Thus $f(x) = a$, $f(x) = \lfloor x \rfloor$, and $f(x) = \lfloor x^2 \rfloor + a$ work, covering the first, fourth, and third class of answers respectively. Furthermore, it is not hard to show that $f(x) = a + \mathbf{1}_{x>0}$ also works to cover the second class.

Let $P(x, y)$ denote the condition. To prove that nothing else works, the key result is to prove an "intermediate value theorem": if $a$ and $b$ are in the range of $f$, then so is every integer between $a$ and $b$. Let's first see how this finishes. If we assume the intermediate value theorem, then all we need to show is that if the range of $f$ is at least 2, then the range of $f$ is unbounded above. Indeed, if $f(x) - f(y) \ge 2$, then $P(x, y - x)$ gives us that $f(2x - y) > f(x)$, so iterating this procedure finishes.

We will now prove the intermediate value theorem. We will repeatedly use the fact that if $f(x)$ is a solution, so is $f(ax + b) + c$ for $a, b \in \mathbb{R}$ and $c \in \mathbb{Z}$.

Lemma 1.1
If $f(0) \le -1$, then $f(2^k) \ge 2^k f(1)$ for $k \ge 0$.
Proof. $P(2^k, 2^k)$ yields that $f(2^{k+1}) \ge 2f(2^k)$. $\square$

Lemma 1.2
If $f(-1) \le -2$ and $f(0) = 0$, then $f(2^k) \ge 2^k - 1$ for all positive integers $k$.
Proof. Applying Lemma 1.1 to $f(x-1)+1$ yields that $f(2^k-1) \ge 2^k-1$. Then, applying Lemma 1.1 to $f(2^k-x) - f(2^k)-1$ yields that
$$f(0) - f(2^k) - 1 \ge 2^k(f(2^k - 1) - f(2^k) - 1) \implies f(2^k) + 1 \ge \frac{2^k f(2^k - 1)}{2^k - 1} \ge 2^k. \quad \square$$

Now to prove the intermediate value theorem, scale and shift such that $f(-1) \le -2$ and $f(0) = 0$; it suffices to show that there exists some number strictly between $f(-1)$ and $f(0)$ in the range of $f$ (since by iteration we can then get all values). Suppose not and let $a_k = f(-1/2^k)$. If $k$ is minimal such that $a_k \ge 0$, then $P(-1/2^k, 1/2^k)$ yields a contradiction. Thus $a_k \le -2$ for all $k$. However, applying Lemma 1.2 to $f(x/2^k)$ yields that $a_k \le -2 \implies f(1) \ge 2^k - 1$, which cannot hold for all $k$ since $f(1)$ is constant.