Find all functions $f\colon \mathbb{Z} \rightarrow \mathbb{Z}$ such that, for all integers $m$ and $n$,$$f(f(m)-n)+f(f(n)-m)=f(m+n).$$ Espen Slettnes and Luke Robitaille
Problem
Source: ELMO 2022 P6
Tags: functional equation, algebra, ELMO 2022
24.06.2022 06:24
The answer is $f(x)\equiv 2x$ and $f(x)\equiv 0$. Claim 1: $f(0)=0$. Proof of claim: Let $k=f(0)$. $P(0,0) \rightarrow 2f(f(0))=f(0)$ so $f(k)=\frac k2$. $P(0,k)\rightarrow f(0)+f(f(k))=f(k)$. Thus, $f(f(k))=-\frac k2$ $P(f(k),f(k))\rightarrow 2f(f(f(k))-f(k))=f(2f(k))$ $2f(-\frac k2 - \frac k2)=f(k)=\frac k2$ $f(-k)=\frac k4$ $P(0,f(k)) \rightarrow f(k-f(k))+f(f(f(k)))=f(f(k))$ Note $k-f(k)=f(k)$ so $f(f(f(k)))=0$ $P(f(f(k)),f(f(k))) \rightarrow 2f( f(f(f(k))) - f(f(k))) = f(2f(f(k))) = f(-k)$ So $2f( -f(f(k))) = f(-k)=\frac k4$ $-k=2f(f(k))=2f\left(\frac k2\right)=\frac k4$ Therefore, $k=0$. Now we make some useful substitutions: By $P(n,n), f(2n)=2f(f(n)-n)$ Therefore, $P(f(f(n)-n)-n,n)$ satisfies $f(2n)-(f(f(n)-n)-n) = 2n + f(f(n)-n)-n$. Therefore, $$f( f(f(f(n)-n)-n) - 2n) = 0$$ Also, $P(m, f(m)-m)$ yields $$f(m) + f( f(f(m)-m) - m) = f(f(m))$$ $P(m,0)$ yields $f(f(m))+f(-m)=f(m)$ Thus, $$f(-m)+f( f(f(m)-m) - m) = (f(m)-f(f(m))) + (f(f(m))-f(m))=0$$ Case 1: $f(x)=0 \rightarrow x=0$. This means $f(f(f(n)-n)-n)=2n$. Plugging that into the above equation yields $f(-m)=-2m$, so $f(x)\equiv 2x$. Case 2: $f(a)=0$ for some $a$. Let $S=\{ x| f(x)=0\}$. By $P(m,0)$, if $m\in S$ then $-m\in S$. By $P(m,n)$ for $m,n\in S$, $m+n\in S$, so there exists an positive integer $t$ such that $S=t\mathbb{Z}$ Claim: $t$ is odd. Proof: Assume $t$ is even. $P(\frac t2, \frac t2) \colon$ $$f\left(f\left(\frac t2\right) - \frac t2\right)=0 \rightarrow f\left(\frac t2\right) \equiv \frac t2(\bmod\; t)$$ But $P(-t,\frac{t}{2})$ yields $$f\left( f\left(\frac{t}{2}\right)-t\right) =0$$ So $t\mid f\left(\frac t2\right)$. The two equivalences contradict each other. We can apply the same argument to get $f(f(f(n)-n)-n)\equiv 2n(\bmod\; t)$, so $f(-n)\equiv -2n(\bmod\; t)$ for all $n$. The next part is to use the pseudo-linearity of $f$: suppose $t\nmid m$ $P(kt, m): f(-m) + f(f(m)-kt)=f(m+kt)$ Therefore, for all $x\equiv m(\bmod\; t)$, $f(x) - f(m+f(m)-x) = f(-m)$ Suppose there exists $m,n$ such that $m\equiv n(\bmod\; t)$ and $m+f(m)\ne n+f(n)$. Recall $f(m)\equiv 2m(\bmod\; t)$ For all $x\equiv m(\bmod\; t)$, we have $$f(x)-f(m+f(m)-x)=f(-m)$$ $$f(x)-f(n+f(n)-x)=f(-n)$$ Therefore, $$f(m+f(m)-x) - f(n+f(n)-x) = f(-n) - f(-m)$$ Note $m+f(m)-x\equiv 2m(\bmod\; t)$. Therefore, for all $y\equiv 2m(\bmod\; t), f(y)-f((n+f(n)-m-f(m))+y)=E$ where $E=f(-n)-f(-m)$ and $-D=n+f(n)-m-f(m)$, which is a nonzero multiple of $t$. Hence, for all $y\equiv 2m(\bmod\; t)$, $$f(y)-f(y-D)=E$$ Since $t\mid D,$ $$f(y)-f(y-kD)=Ek$$for all integers $k$. Similarly, for all $y\equiv m(\bmod\; t), f(y)-f(y-D)=-E$ (or you can check that $f(m+D)-f(f(m)-D)=f(m)-f(f(m))=f(-m)$) Therefore, $P(m,m)$ compared to $P(m+D^2,m)$ gives $$f(m+D^2+m)-f(m+m) = f(f(m+D^2)-m)-f(f(m)-m) + f(f(m)-m-D^2)-f(f(m)-m)$$ $$ED=f(f(m)+ED-m)-f(f(m)-m) + ED$$ $$0=E^2$$ Therefore, $E=0$. This yields that $f(m), f(m+t), \cdots,$ is periodic because for all $x\equiv m(\bmod\; t), f(x)=f(x+D)$. Let $M$ be the maximum absolute value of $f(x+kt)$ over all integers $k$. We can pick $\alpha$ such that $2^M\mid \alpha$ and $\alpha\equiv m(\bmod\; t)$. We can induct on $k$ to show $2^k\mid f(j)$ if $2^k\mid j$ for all integers $k,j$. Therefore, $|f(\alpha)|>M$ (which is not possible by the maximality of $M$) or $f(\alpha)=0$, but $t\nmid \alpha$, absurd! The other case, where $m+f(m)=n+f(n)$ for all $m\equiv n(\bmod\; t)$, can be handled in the exact same way, because $f(n)-f(n-t)=-t$ and the same strategy applies. Remark: Another way to finish (without pseudo-linearity) is to do injectivity over $r+t\mathbb{Z}$ to show that $f(x+kt)_{k\in \mathbb{Z}}$ is injective or periodic.
24.06.2022 06:39
This problem is so brutal. The solution is so long that I will split it into five parts. All answers $f(x)=0$ and $f(x)=2x$. They obviously work. Let the given assertion be $P(m,n)$.
26.06.2022 20:02
Quote: From Part 4, we have either $D\mid x$ or $f(2x)=4x$. So how does it follow by Part 4? How did you manage to prove that it can't be $f(2x)=4x-D$ or something else?
27.06.2022 03:07
I used Part 4 with $f(f(2x)-x)=f(3x)$. It gives that either $f(3x)=0\implies D\mid x$ or $f(2x)-x=f(3x)$.
27.06.2022 05:16
How does this follow?
why does that force?
27.06.2022 05:53
YaoAOPS wrote:
How does this follow?
why does that force? Please read the full solution before troubling sir MarkBcc to explain his sol again and again. The first part follows because \(D\) is odd, and the second part follows because, \(f(x)=0\) implies \(D\mid x\) and so \(D\mid a+kd\implies D\mid a\).
27.06.2022 05:58
For the first part, $D$ being odd doesn't show why it divides $2(a + b) - 2a$, and for the second part I was referring to how it was forced, not the logic afterwards. I've also had read the full solution when I had asked those questions, but I'll go do some more thinking about how the two parts follow.
27.06.2022 06:10
YaoAOPS wrote: For the first part, $D$ being odd doesn't show why it divides $2(a + b) - 2a$, and for the second part I was referring to how it was forced, not the logic afterwards. I've also had read the full solution when I had asked those questions, but I'll go do some more thinking about how the two parts follow. Again you haven't read it properly Like, the second part follows because \(2^x|y\) and \(x>y\) of course means \(y=0\) lol. For the first part, see the part 2 of sir MarkBcc's solution. He proved that \(f(f(x)-2x)=0\) so \(D\mid f(a)-2a\) and also \(D\mid f(a+b)-2(a+b)\). But as \(f(a)=f(a+b)\), subtract the two divisibilities and u get the desired result. I hope I resolve your doubt?
27.06.2022 06:20
@rama1728 please don't say he hasn't read properly. Sometimes things just don't click to people. This being said, I see all questions directed to MarkBcc's solution. Any questions or comments about my solution is welcome too!
27.06.2022 06:27
CANBANKAN wrote: @rama1728 please don't say he hasn't read properly. Sometimes things just don't click to people. This being said, I see all questions directed to MarkBcc's solution. Any questions or comments about my solution is welcome too! Your solution is new and nice! Oh no like, the 5 posts between me and the OP is not very useful, so i said, if he reads properly and more focusedly, we wouldn't have to keep this discussion and the thread will be filled with cool and awesome solutions Don't take me wrong.
27.06.2022 06:49
My solution shares parts 1-3 of the official sol and the $2^K$ idea. It uses quasi-linearity/pseudo-linearity and has a slightly different finish, so it's not *that* different/new. On another note, @YaoAOPS, I highly recommend using a pencil or paper to help you think about why the steps follow instead of asking others to feed you the answer if you are really struggling to follow along.
04.11.2022 17:19
Why ? f(f(A)-2x)=0
23.11.2023 07:39
Is this what the kids are into these days? Let $P(m,n)$ denote the assertion. Step 1: $f(0)=0$ $$P(0,0) => 2f^2(0)=f(0)$$$$P(f(0),0) => f^3(0)+f(0)=f^2(0)$$$$P(f(f(0)),0) => f^4(0)+f(f(0)-f^2(0))=f^4(0)+f^3(0)=f^3(0)$$$$ => f^4(0)=0$$$$P(0, -f^2(0)) => f(f(0)+f^2(0))+f(0)=0 $$$$ => f(f(0)+f^2(0))=-f(0)$$ $$P(f^3(0),f^3(0)) => 2f^3(0)=f(2f^3(0))=f(-f(0))$$$$P(-f(0), f^3(0)) => 0 + f^2(0)=f(f^3(0)-f(0)$$$$P(f(0),f^2(0)) => f(f^3(0)-f(0))+f(0)=f(f(0)+f^2(0))$$$$ => f^2(0)=-2f(0)$$$$ => f(0) = 0$$Now split into two cases. Case 1: $f(x)=0 \iff x=0$ I claim the only solution in this case is $f(x)\equiv 2x$. $$P(m,0)\rightarrow f(-m)+f^2(m)=f(m)$$$$P(m,m)\rightarrow 2f(f(m)-m)=f(2m)$$$$\rightarrow 2|f(2m)$$$$P(2m,\frac{f(2m)-2m}{2}) \rightarrow f(f(2m)-\frac{f(2m)-2m}{2}) + f(f(\frac{f(2m)-2m}{2})-2m)=f(2m+\frac{f(2m)-2m}{2})$$$$\iff f(f(\frac{f(2m)-2m}{2})-2m)=0$$$$\iff f(\frac{f(2m)-2m}{2})=2m$$Thus the range of $f$ includes all even numbers. From $-f(-m)=f^2(m)-f(m)$, and the fact that the LHS can take on all even values, we get that $\frac{f^2(m)-f(m)}{2}$ is surjective over the integers. Since $f(m)$ can take on any even value, we replace this with $\frac{f(2m)-2m}{2}$ being surjective over the integers. Now as we vary $\frac{f(2m)-2m}{2}$ over the integers in the equation $f(\frac{f(2m)-2m}{2})=2m$, the LHS will take on all possible integer values, and the RHS will take on all even values exactly once. This implies that $f$ must be injective. From here we can easily finish this case. $$P(f(m),m) \rightarrow f(f^2(m)-m)+f(0)=f(f(m)+m) $$$$\rightarrow f^2(m)-m=f(m)+m$$Combining this with $f(-m)+f^2(m)=f(m)$, we get that $f(-m)=-2m$, finishing this case. Case 2: there exists an $x \neq 0$ such that $f(x)=0$ Then from $f(x)=f(-x)+f^2(x)$, we get that $f(-x)=0$ as well. Suppose $f(a)=f(b)=0$. Then $$P(a,b) \rightarrow f(f(a)-b)+f(f(b)-a)=f(a+b)$$$$\iff f(-b)+f(-a)=f(a+b)$$$$\iff f(a+b)=0$$So the set of roots of the function form a group under addition. WLOG say the roots are such that $f(x)=0 \equiv k|x$ for some fixed $k$. Now setting $$P(m,kx) \rightarrow f(f(m)-kx)+f(f(kx)-m)=f(m+kx),$$which implies that $f(m+kx)-f(f(m)-kx)$ is independent of $x$. By performing the bijection $g$ defined as $g(m,x) = g(m+k,x-1)$ repeatedly, we get that if we apply $g$ $y$ times that $f(m+kx)-f(f(m+ky)+ky-kx)$ is independent of $x$ as well. This means that the value of $f(f(m+ky)+ky-kx)$ only depends on $m$ and $y$. The most important part of this shifts of $k$ have the same impact on, say, $f(f(m))$ and $f(f(m+k)+k)$. Now look at things modulo $k$ for a little bit. By infinite pigeonhole we should be able to find some $m$ in each mod $k$ residue class such that $f(m+ky) \equiv f(m)$ modulo $k$, then by our shifts of $k$ will eventually move one of these onto the other one, implying that the shifts will also repeat. Now that the values of the shifts of $f(f(m))$ repeat, apply this back one step since $f(m+kx)-f(f(m)-kx)$ is independent of $x$, we get that the values of the shifts of $f(m)$ will always repeat. Since we did this for all residue classes, it must be the case that the shifts of $k$ for any starting number will eventually repeat. This implies that we can find some $X$ (e.g. the least common multiple of all the other shift repeat periods) such that $f$ is linear on each mod $X$ residue class (i.e. $f(x+X)-f(x)=f(x+2X)-f(x+X)$). let $g(x)=f(x+X)-f(x)$. Obviously $g(x+X)=g(x)$, and $f(X)=0$. Now look back at our original functional equation. $$f(f(m)-n)+f(f(n)-m)=f(m+n)$$Let $A=g(m)$, $B=g(f(m)-n)$, $C=g(n)$, $D=g(f(n)-m)$, and $E=g(m+n)$. Let the finite set $S$ denote the range of $g$. Consider replacing $m$ with $m+X^2$. Then examining how this affects our Rearrange this to $AB=X(D+E)$. Let $Y$ be the least common multiple of the values of $S$. Then we have $XY | AB$. Let $A=aY$ and let $B=bY$. Then we have $X | Yab$. Now choose any prime $p$ dividing $X$. If it is the case that $v_p(X) > v_P(Y)$, then by picking $a$ and $b$ such that $v_p(a)=v_p(b)=0$, we get a contradiction. Thus we must have $X|Y$, so all elements of $S$ are divisible by $X$. Now replace $A,B,C,D,E$ in our above two equations with $aX,bX,cX,dX,eX$. Then they rewrite as $$ab-d=e$$and $$-b+cd=e$$. Now if we choose $a=b$ to be the largest possible magnitude, we get that $a^2 \le 2|a|$, which implies that the only possible values of $a,b,c,d,e$ are $-2,-1,0,1,2$. Let $s$ denote the set of possible values of these. Clearly $s$ is a subset of {$-2,-1,0,1,2$} which contains $0$ (since roots repeat every $k$). Now substituting $n=Xy$, we get that $f(f(m)-Xy)-f(m+Xy)$ is independent of $y$. This means that $g(f(m))=-g(m)$. Now looking at $f^2(m)+f(-m)=f(m)$, and considering the map $m \rightarrow m+X$, we get that $$g(m)g(f(m))-g(-m)=g(m)$$$$\iff -g(-m)=g(m)+(g(m))^2.$$Now if $g(m)$ can equal $2$, we get a contradiction because the RHS is too big. Since $s$ containing $x$ implies that $s$ contains $-x$, we get that $s$ does not contain $2$ or $-2$. Now if $1$ is in $s$, we can again substitute this into the above equation to get the RHS is too big. So $-1$ is not in $s$ either, so $f$ must be periodic. Subsituting $P(m,m)$ gives us $2f(f(m)-m)=f(2m)$. I claim that $v_2(f(x)) \ge v_2(x)$. We can prove this by induction by assuming it is true for some $x$ and subsituting $m=2^x \cdot (2y+1)$ into the above thing, showing that our statement above is still true for $x+1$. Now I prove by induction on $v_2(X)$ (where $X$ is here the period) that all functions satisfying the above properties are the zero function. For the base case, if $v_2(X)=0$, this follows using the fact that $v_2(f(2^x))\ge v_2(2^x)$, and since $2^x$ hits all the residue classes modulo $X$ infinitely often. Suppose we have proved the claim up to $v_2(X)=k$. Now suppose $v_2(X)=k+1$. Observe that the function $h(x)=\frac{1}{2}f(2x)$ satisfies the original functional equation by plugging it in, and since $h(x)$ has period $\frac{X}{2}$, it follows that $h(x)$ is the zero function, so $f(x)$ must be zero on all evens. If we suppose for sake of contradiction that $f$ is not the zero function, then since the roots form a group, $f(x)$ must be nonzero on all odds. Now from the fact that $0=f(2m)=2f(f(m)-m)$, we get that $f(m)-m$ is always even. This implies that $f(m)$ is odd for odd $m$. This means that $f(x) \equiv x$ modulo $2$. However if we plug in $(m,n)=(0,1)$ into our functional equation and evaluating modulo $2$, we now get a contradiction. This was really hard. Congrats to CANBANKAN for in-contest solve.
27.03.2024 06:30
The only solutions are $\boxed{f\equiv 0}$ and $\boxed{f(x) = 2x}$ for any integer $x$, which clearly work. Let $P(m,n)$ be the given assertion. Claim: $f(0) = 0$. Proof: $P(0,0): 2f(f(0)) = f(0)$, hence $f(0)$ is even. Let $f(0) = 2c$. We have $f(2c) = c$. $P(m,0): f(f(m)) + f(2c - m) = f(m)$. $P(2c,0): f(f(2c)) + 2c = c$, so $f(f(2c)) = f(c)= -c$. But $P(c,0): f(f(c)) = 0$, so $f^4(0) = 0$. $P(2c,-c): f(f(2c) + c) + f(f(-c) - 2c) = f(c)$, so $f(2c) + f(-2c) = f(c)$, meaning that $f(-2c) = f(c) - f(2c) = -c - c = -2c$. $P(c,c): 2f(f(c) - c) = f(2c)$, hence $2f(-2c) = f(2c)$, so $-4c = c$, so $c = 0$. $\square$ $P(m,m): 2f(f(m) - m) = f(2m)$. Case 1: $f$ is injective at $0$ $P(2m, f(f(m) - m) - m): f( f( f( f(m) - m) - m) - 2m) = 0$, so $f( f( f(m) - m) - m) = 2m$. $P(m, f(m) - m): f(m) + f( f(f(m) - m) - m) = f(f(m))$, so $f(m) + 2m = f(f(m))$. $P(m,0): f(f(m)) + f(-m) = f(m)$. Hence $f(m) + 2m + f(-m) = f(m)$, meaning that $f(-m) = -2m$, so $f(m) = 2m$ for all integers $m$. Case 2: $f$ is not injective at $0$. Notice that if $f(a) = 0$, then $P(a,0)$ gives that $f(-a) = 0$. So then if $f(a) = f(b) = 0$, $P(a,b)$ gives that $f(a+b) = 0$ since $f(-a) = f(-b) =0$. Hence if $f(a) = 0$, $f(x \cdot a) = 0$ for any integer $x$. Now let $d$ be the smallest positive integer with $f(d) = 0$. It's clear that $f(x) = 0 \iff d\mid x$. Again, $P(2m, f(f(m) - m) - m)$ gives that \[f( f( f( f(m) - m) - m) - 2m) = 0,\]hence $ f( f(f(m) - m) - m) \equiv 2m \pmod d$. Claim: $f(m) \equiv 2m \pmod d$ for any integer $m$. Proof: Again, $P(2m, f(f(m) - m) - m)$ gives that \[f( f( f( f(m) - m) - m) - 2m) = 0,\]hence $ f( f(f(m) - m) - m) \equiv 2m \pmod d$. $P(m, f(m) - m): f(m) + f( f(f(m) - m) - m) = f(f(m))$, so $f(f(m)) - f(m) \equiv 2m \pmod d$. However, $P(m,0)$ gives that $f(f(m)) - f(m) = -f(-m)$, meaning that $f(-m) \equiv -2m \pmod d$, so $f(m) \equiv 2m \pmod d$ for all integers $m$. $\square$ This implies that \[ f(f(m) - 2m) = 0\]for all integers $m$. Subcase 2.1: $d$ is odd $P(m, f(m) - 2m): f(2m) + f(-m) = f(f(m) - m)$. However, $f(2m) = 2 f(f(m) - m)$, so $f(-m) = - f(f(m) - m)$, meaning that $2f(-m) = -f(2m)$. This implies that $f(4m) = -2 f(-2m) = 4f(m)$. Claim: If $f(a) = f(b)$ for some $a \ne b$, then $a\equiv b \equiv 0\pmod d$. Notice that if $f(a) = f(b)$, then $2a \equiv 2b \pmod d$, so $d\mid 2(a-b)\implies d\mid a-b$. By comparing $P(a,0)$ and $P(b,0)$, we see that $f(-a) = f(-b)$. Now, notice that $2f(-a) = 2f(-b)$, so $-f(2a) = -f(2b)$, implying that $f(2a) = f(2b)$. Since $2f(f(m) - m) =f(2m)$, we have that $f(f(a) - a) =f(f(b) - b) = f(f(a) - b)$. $P(a, b): f(f(a) - b) + f(f(a) - a) = f(a+b)$, so $2f(f(a) - a) = f(a+b)$, so $f(2a) = f(a+b)$. $P(a, n d)$ compared with $P(b,n d)$ using that $f(-a) = f(-b)$ gives that $f(a+nd) = f(b+nd)$ for any integer $n$, hence $f(x) = f(x + (b-a))$ for all $x\equiv a\pmod d$. Now, since $a\equiv b\pmod d$, we have $f(x) = f(x + n (b-a))$ for any integer $n$ and $x\equiv a\pmod d$. Choose some $x\equiv a\pmod d$ where $\nu_2(x) = \nu_2(b-a)$. This exists because $d$ is odd. Now choose $N > 0$ such that $4^N - 1$ is a multiple of $\frac{b-a}{2^{\nu_2(b-a)}}$. We find that $b-a\mid x(4^N - 1)$, so $x\cdot 4^N \equiv x \pmod{b-a}$. Let $n$ satisfy $x + n(b-a) = 4^N\cdot x$. We find that $f(x) = f(x + n(b-a))$, so $f(x) = f(4^N \cdot x)$. Note that $f(4m) = 4f(m)$ for any $m$, meaning that $f(4^N x) = 4^N f(x)$, so $f(x) = 4^N f(x)$ for some large $N$, meaning that $f(x) = 0$, so $x \equiv a\equiv b \equiv 0\pmod d$, as desired. $\square$ $P(m,2m): f(f(2m) - m) = f(3m)$ Notice this combined with the claim implies that either $d\mid 3m$ or $f(2m) = 4m$. We have $f(f(m)) - f(m) = -f(-m)$ by $P(m,0)$ and $f(-m) = -f(f(m) - m)$, meaning that $P(m,f(m) - m))$ implies \[ f(f(m) - m) = f( f( f(m) - m) - m) = f( -f(-m) - m)\]Since $d\nmid f(m) - m$ for $d\nmid m$, we can conclude that $f(m) - m = -f(-m) - m$, so $f(m) = -f(-m)$ for all $m$ with $d\nmid m$, and this is true for all $d\mid m$, implying that $f$ is odd. Now, since $f(-m) = -f(f(m) - m)$, so $f(m) = f(f(m) - m)$. For any $m$ with $d\nmid m$, we must have $m = f(m) - m$, so $f(m) = 2m$. $P(1, 2-d): f(f(2-d) - 1) = f(1-d)$. If $d > 1$, then $d\nmid 1 - d$, implying that $f(2-d) - 1 = 1-d$, so $f(2-d) = 2-d$. Hence either $d\mid 2 - d$ or $2 - d =0$, which both imply $d = 2$, absurd since $d$ is odd. Hence $d = 1$, and $f\equiv 0$. $\square$ Subcase 2.2: $d$ is even. Fortunately this is easier. Let $d = 2k$. We see that $f(k) - 2k \equiv 0\pmod{2k}$, so $f(k) \equiv 0\pmod{2k}$. $P(k,k): 2f(f(k) - k) = f(2k) = 0$, so $f(f(k) - k) = 0$, implying that $f(k) \equiv k\pmod{2k}$, absurd. $\square$ Therefore, $f\equiv 0$ and $f(x) = 2x$ are the only solutions.
13.05.2024 20:15
Brilliant FE!