IMO

Renhui Jiuzhang 2015 Exam 1 Q3

Suppose $f:\mathbb Z \to \mathbb Z$ satisfy $f(x-f(y))=f(x)^2+f(2x-f(y)),\forall x,y \in \mathbb Z,$ show that $f(f(x))=0,\forall x \in \mathbb Z.$

From this post on I will try to adopt a more casual tone in expounding the solution, with explanatory text mixing with the solution.

First, we see that the equation does not easily lead itself to non-trivial solution (the $f(x)^2$ term is quite weird), therefore we decide to punish it by repeatedly substituting different values of variables until we can compare the information about the values to find a contradiction.

Setting $x=0, f(-f(y))=f(0)^2 + f(-f(y))$, and cancelling gives $f(0)=0$.

Let $y$ be any integer, substituting $x=f(y)$ will give us $f(0)=f(f(y))^2+f(f(y)).$ Since the LHS vanishes, we thus have $f(f(y))=0$ or $-1,\forall f\in \mathbb Z$. Thus we only have to rule out the latter case and the proof is complete.

Notice that the functional equation, though strange in $\mathbb Z$, behaves benignly when only the parity is concerned: in fact, setting $f(x)=x$, we have a ‘solution’ to it $\mod 2$. Thus we want to consider parity. Setting $y=0$, we have $f(2x)= f(x)-f(x)^2.$ The RHS, incidentally, is always an even number, whereas the LHS is the function value of any even number. Thus $f$ maps even numbers to even numbers. (Note that the same cannot be said of odd numbers as $f(x)=0$ is a solution to the equation.)

We aim to utilise the assumption that $\exists \xi \in \mathbb Z, f(f(\xi))=-1.$ We let $f(\xi)=\eta$, for convenience. Let $y=\xi$ in the original equation, we obtain $f(x-\eta)=f(x)^2+f(2x-\eta)$. Now we implant our initial strategy of trashing the function with repeated substitutions.

Let $x=\eta, y=0$, we find $f(2\eta)=f(\eta)-f(\eta)^2 = -1-1=-2.$ Setting $x=2\eta,y=\xi$, we thus have $f(\eta)=f(2\eta)^2+f(3\eta),$ thus $f(3\eta)= -1 -(-2)^2 =-5$ . We thus know that $-1,-2$ and $-5$ are all contained in the image of $f$.

Setting $f(y)=-2$, we have $f(x+2)=f(x)^2+f(2x+2)\equiv f(x) \mod \,2$.

Setting $f(y)=-1$, we have $f(x+1)=f(x)^2+f(2x+1)$. Setting $x+2$ in the place of $x, \,f(x+3)=f(x+2)^2+f(2x+5)$.

Setting $f(y)=-5$, we have $f(x+5)=f(x)^2+f(2x+5)$.

Subtracting the two equations above, we get

$\displaystyle f(x+3)-f(x+5)=f(x+2)^2 - f(x)^2 \ \ \ \ \ \ \ \ \ \ \ \ (*)$

(This is why we used $x+2$ instead of $x$ when $f(y)=-1$, as that would permit us to subtract and reduce one term.)

Upto this point, we haven’t used any property of $\mathbb Z$ (we haven’t in fact used the parity condition). But in an Olympiad problem, we should aim to use all the given conditions, as the problems are almost always tailored such that the conditions just suffice for a solution using elementary method. Now we observe that the LHS of the equation (*) is the difference between two terms with distance $2$ apart, while the RHS has a factor that is also a difference between two terms with distance $2$ apart, with another factor whose absolute value is at least $1$ if we can make sure it is not zero. We want it to be $1$. This can be done by inequality.

If $\forall x \in \mathbb Z, f(x+2)-f(x)=0$, then $f$ is a constant on even number (with that value being thus $0$ as $f(0)=0$) and a constant on odd number (with that value thus being $-1$ as otherwise $-1$ would not be in the range of $f$.) Now, we have shown that $-2$ is also in the image of the function, thus this is a contradiction.

Thus $\exists x\in \mathbb Z, f(x+2)-f(x)\ne 0$. Consider the set $\{\left \vert f(x+2)-f(x)\right \vert \, | \, f(x+2)-f(x)\ne 0\}$, with its minimal element being attained at $x=\sigma$. Substitute $x=\sigma -3$ into (*), and take absolute value.

$|f(\sigma+2)-f(\sigma)|=|f(\sigma -1)-f(\sigma -3)| |f(\sigma -1)+f(\sigma -3)|$.

By the minimality condition, $\lvert f(\sigma -1)-f(\sigma -3)\rvert \ge \lvert f(\sigma+2)-f(\sigma)\rvert$, and $\lvert f(\sigma -1)+f(\sigma -3)\rvert\ge 1$ because it does not vanish (as the LHS is non-zero)

Multiplying them, we have equality in the face of two inequalities. Thus the two inequalities must have equality holding at the same time, thus $f(\sigma-1)-f(\sigma -3) =\pm 1$ . This is impossible since we have shown above that $f(x) \equiv f(x+2)\mod 2,\forall x\in \mathbb Z.$

Q.E.D.

Comment: The problem is not very difficult, and many alternative methods exist, as the function itself is quite bizarre and repeated substitution per se gives more and more information from which any contradiction would finish the problem off.

The problem is proposed by Qiang Shen, and used in a practice exam at Renhui Jiuzhang MO Tuition Centre (Beijing, China) in 2015.