Anatomy of an FE

Etienne here. Today I want to talk about Problem 6 of the IMO, and my thought process while solving it. The official IMO document provides 7 solutions to this problem, and to me all of them feel strange and unmotivatable at first read (especially the construction!). So I hope to demystify this problem and present it in the simplest and most intuitive way possible.

The Problem

P6. Let $\mathbb{Q}$ be the set of rational numbers. A function $f: \mathbb{Q} \to \mathbb{Q}$ is called aquaesulian if the following property holds: for every $x,y \in \mathbb{Q}$, $$ f(x+f(y)) = f(x) + y \quad \text{or} \quad f(f(x)+y) = x + f(y). $$ Show that there exists an integer $c$ such that for any aquaesulian function $f$ there are at most $c$ different rational numbers of the form $f(r) + f(-r)$ for some rational number $r$, and find the smallest possible value of $c$.

Solution

This problem statement should jump out to anyone as unusual. First, for each pair $(x,y)$, $f$ can choose between two equations. And the statement to be proven is also weird. How does $f(r)+f(-r)$ come into the picture? For now, let's focus on the two equations.

One of the things I love taking advantage of when doing FEs is symmetry. There are two symmetries I notice immediately:

1. Swapping $x$ and $y$ interchanges the two equations.
2. There is some mapping between $x+f(y)$ and $f(x)+y$, by which I mean $f$ sends one to the other, but we don't know which.

The way I've always visualised mappings is with arrows. For example, $$x+f(y)\rightarrow f(x)+y$$ indicates that $f(x+f(y))=f(x)+y$, which would correspond to the first equation in the problem statement. So now we can neatly summarise symmetry #2 by defining a relation between $x+f(y)$ and $y+f(x)$, like so: $$x+f(y) \rightleftharpoons f(x)+y$$ means that there is an arrow from one place to the other, but I don't know which direction it's going.

Using symmetry #1 suggests substituting $(x,x)$, which gives us that $$f(f(x)+x)=f(x)+x.$$ Substituting into this $x=0$ gives $f(f(0))=f(0)$. Now that it feels like I've explored sufficiently, I want to switch gears to try and prove some properties of $f$, namely, I want to prove injectivity, so that I can get $f(0)=0$. So if I set $f(a)=f(b)$, I know that $$a+f(a)=a+f(b)\rightleftharpoons b+f(a)=b+f(b)$$But since $a+f(a)$ and $b+f(b)$ go to themselves, it means the two must be equal, implying $a=b$. So $f$ is injective.

After finishing our observations, let's actually start substituting. Setting $x=-f(y)$ gives $$0\rightleftharpoons f(-f(y))+y$$ But we know that $0\rightarrow 0$! By injectivity, these are the only arrows that can come out of, or go into $0$. So we must have $$f(-f(y))+y=0.$$Note that this also immediately gives me surjectivity, so $f$ is bijective.

Now that I feel like I've made some progress, I want to use my favourite FE technique again. Even if we've exhausted all the trivial symmetries, we can still induce our own symmetries. The expression $f(x)+f(y)$ can be interpreted in two ways (another classic FE technique) as either $f(\cdot)+\cdot$ or $\cdot+f(\cdot)$, so we get: $$x+f(f(y))\rightleftharpoons f(x)+f(y)\rightleftharpoons f(f(x))+y$$The problem is the $f(f(y))$. Now is finally time to introduce $f(r)+f(-r)$! Notice that $f(-f(y))$ has a nice form, so we can consider the expression $f(f(y))+f(-f(y))=f(f(y))-y$. There's no problem with the nested $f(y)$, since $f$ is surjective, so $f(y)$ can take any value. Then$$x+f(f(y))=x-f(-f(y))+f(-f(y))+f(f(y))$$$$=x+y+f(f(y))+f(-f(y))$$This gives us $$x+y+g(y)\rightleftharpoons f(x)+f(y)\rightleftharpoons x+y+g(x)$$ where $g(x)$ denotes $f(f(x))+f(-f(x))$, which is also equal to $f(f(x))-x$.

We can now consider possible values of $g(r)$; if there are at least two different ones, then there exist $x,y$ such that $g(x)\neq g(y)$. This lets us narrow down which ways the arrows go. Clearly both cannot point outward, since the two outside values are unequal. By injectivity they cannot both point inward either. It follows that the point in the same direction, so WLOG $$x+y+g(y)\rightarrow f(x)+f(y)\rightarrow x+y+g(x).$$We can use this result by considering $P(f(x)+f(y),z)$ for arbitrary $z$: $$x+y+z+g(x)\rightleftharpoons f(x)+f(y)+f(z)$$which looks pretty nice. The final step is now to choose an appropriate value of $z$. We derived earlier that $g(x)+x=f(f(x))$, and substituting $z=-f(f(x))$ is nice, because this cancels out the LHS, and $f(-f(f(x)))=-f(x)$, which cancels out terms on the RHS. Doing this just gives $y\rightleftharpoons f(y)$, which is obviously true. But why not exploit the almost-symmetric structure of this equation by substituting $z=-f(f(y))$ instead? This gives $$x+y-f(f(y))+g(x)\rightleftharpoons f(x)$$ which is equivalent to $$x+g(x)-g(y)\rightleftharpoons f(x)$$Since $g(x)\neq g(y)$, by injectivity we must have $$x+g(x)-g(y)\leftarrow f(x)$$But $x+g(x)=f(f(x))$!

So $g(y)=0$. It follows that $g(r)$ can take at most one nonzero value, so it takes two values at most.

Construction

The only thing left to do is to construct. We want a bijective function that satisfies $f(-f(x))=-x$. To make the construction easier, we can note that this is equivalent to $-f(-f(x))=x$, so the function $-f(x)$ is an involution.

Maybe $-f(x)=c-x$ works? This is the most classical example of an involution. The problem is that in our original equation we have $x+y-c\rightleftharpoons x+y-c$ which of course fails for big enough $x$ and $y$. This suggests that I need different constants for each $x$, but also that $x$ and $c_x-x$ need to have the same constant (so they are in the same "class"), where $c_x$ is the constant corresponding to $x$.

Remember also that we had that $f(f(x))-x$ can also only take one nonzero value. Since $f(f(x))-x=-c_{f(x)}-c_x$ this means that $c_{f(x)}+c_x$ must be a constant or zero.

These two facts, that $x$ and $c_x-x$ have the same constant, and that $c_{f(x)}+c_x$ is a constant, should suggest considering fractional parts: if $x$ and $c_x-x$ have the same fractional part, then $x$ and $f(x)=x-c_x$ have opposite fractional parts summing to an integer. We can then see that considering $c_x=2\{x\}$ (where $\{x\}$ denotes the fractional part of $x$) satisfies both of these conditions.

This gives the function $f(x)=x-2\{x\}$, or $f(x)=\lfloor x\rfloor-\{x\}$. We can check that this satisfies the original equation.

Concluding Thoughts

The most important part of this problem is how to interpret the condition. Rather than viewing it as two separate equations, it is necessary to find some way to link them together into one singular condition. I think this is the way a lot of Q3/6s go, in that there is some lens with which to see the problem that will make progression easier (see: Glen's Q3).

The way the conditions are linked is by recognising their symmetry, which is a major theme that is present throughout the solution. A key step was using the symmetry of the two conditions by considering $f(x)+f(y)$ in two ways, which allowed us to make use of the weird $f(-f(x))$ condition in order to finally make sense of the strange $f(r)+f(-r)$ expression.

Finally, I think that some progress on the bound is necessary to conceive the construction, otherwise the consideration of the fractional part seems to come out of thin air. I hope that the way I presented it explains how one can gain some sort of algebraic intuition from the equations that leads to the construction.