International Mathematical Olympiad

Define $g(x)=x-f(x)$. The condition on $f$ then rewrites as follows:
For every $x, y \in \mathbb{R}$ such that $((x+y)-g(x))((x+y)-g(y))>0$, we have $g(x)=g(y)$.
This condition may in turn be rewritten in the following form:
If $g(x) \neq g(y)$, then the number $x+y$ lies (non-strictly) between $g(x)$ and $g(y)$.
Notice here that the function $g_{1}(x)=-g(-x)$ also satisfies $(*)$, since
$$\begin{gathered} g_{1}(x) \neq g_{1}(y) \Longrightarrow \quad g(-x) \neq g(-y) \quad \Longrightarrow \quad-(x+y) \text{ lies between } g(-x) \text{ and } g(-y) \\ \Longrightarrow \quad x+y \text{ lies between } g_{1}(x) \text{ and } g_{1}(y) \end{gathered}$$
On the other hand, the relation we need to prove reads now as
$$\begin{equation*} g(x) \leqslant g(y) \quad \text{ whenever } x<y \tag{1} \end{equation*}$$
Again, this condition is equivalent to the same one with $g$ replaced by $g_{1}$.
If $g(x)=2 x$ for all $x \in \mathbb{R}$, then (*) is obvious; so in what follows we consider the other case. We split the solution into a sequence of lemmas, strengthening one another. We always consider some value of $x$ with $g(x) \neq 2 x$ and denote $X=g(x)$.

Lemma 1. Assume that $X<2 x$. Then on the interval $(X-x ; x]$ the function $g$ attains at most two values - namely, $X$ and, possibly, some $Y>X$. Similarly, if $X>2 x$, then $g$ attains at most two values on $[x ; X-x)$ - namely, $X$ and, possibly, some $Y<X$.

Proof. We start with the first claim of the lemma. Notice that $X-x<x$, so the considered interval is nonempty.
Take any $a \in(X-x ; x)$ with $g(a) \neq X$ (if it exists). If $g(a)<X$, then $(*)$ yields $g(a) \leqslant a+x \leqslant g(x)=X$, so $a \leqslant X-x$ which is impossible. Thus, $g(a)>X$ and hence by (*) we get $X \leqslant a+x \leqslant g(a)$.
Now, for any $b \in(X-x ; x)$ with $g(b) \neq X$ we similarly get $b+x \leqslant g(b)$. Therefore, the number $a+b$ (which is smaller than each of $a+x$ and $b+x$ ) cannot lie between $g(a)$ and $g(b)$, which by (*) implies that $g(a)=g(b)$. Hence $g$ may attain only two values on ( $X-x ; x$ ], namely $X$ and $g(a)>X$.
To prove the second claim, notice that $g_{1}(-x)=-X<2 \cdot(-x)$, so $g_{1}$ attains at most two values on $(-X+x,-x]$, i.e., $-X$ and, possibly, some $-Y>-X$. Passing back to $g$, we get what we need.

Lemma 2. If $X<2 x$, then $g$ is constant on $(X-x ; x)$. Similarly, if $X>2 x$, then $g$ is constant on $(x ; X-x)$.

Proof. Again, it suffices to prove the first claim only. Assume, for the sake of contradiction, that there exist $a, b \in(X-x ; x)$ with $g(a) \neq g(b)$; by Lemma 1 , we may assume that $g(a)=X$ and $Y=g(b)>X$.
Notice that $\min \{X-a, X-b\}>X-x$, so there exists a $u \in(X-x ; x)$ such that $u<\min \{X-a, X-b\}$. By Lemma 1, we have either $g(u)=X$ or $g(u)=Y$. In the former case, by (*) we have $X \leqslant u+b \leqslant Y$ which contradicts $u<X-b$. In the second case, by (*) we have $X \leqslant u+a \leqslant Y$ which contradicts $u<X-a$. Thus the lemma is proved.

Lemma 3. If $X<2 x$, then $g(a)=X$ for all $a \in(X-x ; x)$. Similarly, if $X>2 x$, then $g(a)=X$ for all $a \in(x ; X-x)$.

Proof. Again, we only prove the first claim.
By Lemmas 1 and 2, this claim may be violated only if $g$ takes on a constant value $Y>X$ on ( $X-x, x$ ). Choose any $a, b \in(X-x ; x)$ with $a<b$. By (*), we have
$$\begin{equation*} Y \geqslant b+x \geqslant X \tag{2} \end{equation*}$$
In particular, we have $Y \geqslant b+x>2 a$. Applying Lemma 2 to $a$ in place of $x$, we obtain that $g$ is constant on $(a, Y-a)$. By (2) again, we have $x \leqslant Y-b<Y-a$; so $x, b \in(a ; Y-a)$. But $X=g(x) \neq g(b)=Y$, which is a contradiction.

Now we are able to finish the solution. Assume that $g(x)>g(y)$ for some $x<y$. Denote $X=g(x)$ and $Y=g(y)$; by ( $*$ ), we have $X \geqslant x+y \geqslant Y$, so $Y-y \leqslant x<y \leqslant X-x$, and hence $(Y-y ; y) \cap(x ; X-x)=(x, y) \neq \varnothing$. On the other hand, since $Y-y<y$ and $x<X-x$, Lemma 3 shows that $g$ should attain a constant value $X$ on ( $x ; X-x$ ) and a constant value $Y \neq X$ on $(Y-y ; y)$. Since these intervals overlap, we get the final contradiction.

As in the previous solution, we pass to the function $g$ satisfying (*) and notice that we need to prove the condition (1). We will also make use of the function $g_{1}$.
If $g$ is constant, then (1) is clearly satisfied. So, in the sequel we assume that $g$ takes on at least two different values. Now we collect some information about the function $g$.

Claim 1. For any $c \in \mathbb{R}$, all the solutions of $g(x)=c$ are bounded.

Proof. Fix any $y \in \mathbb{R}$ with $g(y) \neq c$. Assume first that $g(y)>c$. Now, for any $x$ with $g(x)=c$, by (*) we have $c \leqslant x+y \leqslant g(y)$, or $c-y \leqslant x \leqslant g(y)-y$. Since $c$ and $y$ are constant, we get what we need.
If $g(y)<c$, we may switch to the function $g_{1}$ for which we have $g_{1}(-y)>-c$. By the above arguments, we obtain that all the solutions of $g_{1}(-x)=-c$ are bounded, which is equivalent to what we need.
As an immediate consequence, the function $g$ takes on infinitely many values, which shows that the next claim is indeed widely applicable.

Claim 2. If $g(x)<g(y)<g(z)$, then $x<z$.

Proof. By (*), we have $g(x) \leqslant x+y \leqslant g(y) \leqslant z+y \leqslant g(z)$, so $x+y \leqslant z+y$, as required.

Claim 3. Assume that $g(x)>g(y)$ for some $x<y$. Then $g(a) \in\{g(x), g(y)\}$ for all $a \in[x ; y]$.

Proof. If $g(y)<g(a)<g(x)$, then the triple ( $y, a, x$ ) violates Claim 2. If $g(a)<g(y)<g(x)$, then the triple $(a, y, x)$ violates Claim 2. If $g(y)<g(x)<g(a)$, then the triple $(y, x, a)$ violates Claim 2. The only possible cases left are $g(a) \in\{g(x), g(y)\}$.

In view of Claim 3, we say that an interval $I$ (which may be open, closed, or semi-open) is a Dirichlet interval* if the function $g$ takes on just two values on $I$.
Assume now, for the sake of contradiction, that (1) is violated by some $x<y$. By Claim 3, $[x ; y]$ is a Dirichlet interval. Set
$r=\inf \{a:(a ; y]$ is a Dirichlet interval $\}$ and $s=\sup \{b:[x ; b)$ is a Dirichlet interval $\}$.
Clearly, $r \leqslant x<y \leqslant s$. By Claim 1, $r$ and $s$ are finite. Denote $X=g(x), Y=g(y)$, and $\Delta=(y-x) / 2$.
Suppose first that there exists a $t \in(r ; r+\Delta)$ with $f(t)=Y$. By the definition of $r$, the interval ( $r-\Delta ; y$ ] is not Dirichlet, so there exists an $r^{\prime} \in(r-\Delta ; r]$ such that $g\left(r^{\prime}\right) \notin\{X, Y\}$.
The function $g$ attains at least three distinct values on $\left[r^{\prime} ; y\right]$, namely $g\left(r^{\prime}\right), g(x)$, and $g(y)$. Claim 3 now yields $g\left(r^{\prime}\right) \leqslant g(y)$; the equality is impossible by the choice of $r^{\prime}$, so in fact $g\left(r^{\prime}\right)<Y$. Applying (*) to the pairs ( $r^{\prime}, y$ ) and ( $t, x$ ) we obtain $r^{\prime}+y \leqslant Y \leqslant t+x$, whence $r-\Delta+y<r^{\prime}+y \leqslant t+x<r+\Delta+x$, or $y-x<2 \Delta$. This is a contradiction.

Thus, $g(t)=X$ for all $t \in(r ; r+\Delta)$. Applying the same argument to $g_{1}$, we get $g(t)=Y$ for all $t \in(s-\Delta ; s)$.
Finally, choose some $s_{1}, s_{2} \in(s-\Delta ; s)$ with $s_{1}<s_{2}$ and denote $\delta=\left(s_{2}-s_{1}\right) / 2$. As before, we choose $r^{\prime} \in(r-\delta ; r)$ with $g\left(r^{\prime}\right) \notin\{X, Y\}$ and obtain $g\left(r^{\prime}\right)<Y$. Choose any $t \in(r ; r+\delta)$; by the above arguments, we have $g(t)=X$ and $g\left(s_{1}\right)=g\left(s_{2}\right)=Y$. As before, we apply (*) to the pairs $\left(r^{\prime}, s_{2}\right)$ and $\left(t, s_{1}\right)$ obtaining $r-\delta+s_{2}<r^{\prime}+s_{2} \leqslant Y \leqslant t+s_{1}<r+\delta+s_{1}$, or $s_{2}-s_{1}<2 \delta$. This is a final contradiction.