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)\ne 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 $(\ast )$, since $$\begin{array}{c}{g}_1(x)\ne g_1(y)⟹g(-x)\ne g(-y)⟹-(x+y)\text{ lies between }g(-x)\text{ and }g(-y)\\ ⟹x+y\text{ lies between }{g}_1(x)\text{ and }{g}_1(y)\end{array}$$ On the other hand, the relation we need to prove reads now as $$\begin{array}{c}g(x)⩽g(y)\text{ whenever }x<y\end{array}\text{\hspace{1em}(1)}$$ Again, this condition is equivalent to the same one with $g$ replaced by $g_1$. If $g(x)=2x$ 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)\ne 2x$ and denote $X=g(x)$.

Lemma 1. Assume that $X<2x$. 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>2x$, 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)\ne X$ (if it exists). If $g(a)<X$, then $(\ast )$ yields $g(a)⩽a+x⩽g(x)=X$, so $a⩽X-x$ which is impossible. Thus, $g(a)>X$ and hence by () we get $X⩽a+x⩽g(a)$. Now, for any $b\in (X-x;x)$ with $g(b)\ne X$ we similarly get $b+x⩽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<2x$, then $g$ is constant on $(X-x;x)$. Similarly, if $X>2x$, 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)\ne 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⩽u+b⩽Y$ which contradicts $u<X-b$. In the second case, by () we have $X⩽u+a⩽Y$ which contradicts $u<X-a$. Thus the lemma is proved.

Lemma 3. If $X<2x$, then $g(a)=X$ for all $a\in (X-x;x)$. Similarly, if $X>2x$, 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{array}{c}Y⩾b+x⩾X\end{array}\text{\hspace{1em}(2)}$$ In particular, we have $Y⩾b+x>2a$. 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⩽Y-b<Y-a$; so $x,b\in (a;Y-a)$. But $X=g(x)\ne 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 ( $\ast$ ), we have $X⩾x+y⩾Y$, so $Y-y⩽x<y⩽X-x$, and hence $(Y-y;y)\cap (x;X-x)=(x,y)\ne \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\ne X$ on $(Y-y;y)$. Since these intervals overlap, we get the final contradiction.

---

Alternative solution.

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)\ne c$. Assume first that $g(y)>c$. Now, for any $x$ with $g(x)=c$, by () we have $c⩽x+y⩽g(y)$, or $c-y⩽x⩽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)⩽x+y⩽g(y)⩽z+y⩽g(z)$, so $x+y⩽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⩽x<y⩽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)⩽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⩽Y⩽t+x$, whence $r-\Delta +y<r^{\prime }+y⩽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⩽Y⩽t+s_1<r+\delta +s_1$, or $s_2-s_1<2\delta$. This is a final contradiction.