Find all functions $f:\mathbb{R}\to \mathbb{R}$ such that for all $x,y\in \mathbb{R}$ one has \[f(f(x)+y)=f(x+f(y))\]and in addition the set $f^{-1}(a)=\{b\in \mathbb{R}\mid f(b)=a\}$ is a finite set for all $a\in \mathbb{R}$.
Problem
Source: 2020 Israel Olympic Revenge P1
Tags: functional equation, algebra, olympic revenge, function, symmetry
16.06.2022 14:08
I have a very long-winded solution, hopefully there's a shorter one. Let $R$ be the range of $f$, and let $T$ be the set of real numbers $t$ satisfying $f(t+f(x)+y)=f(t+x+f(y))$ for all $x,y \in \mathbb{R}$. Clearly $0 \in T$. If $t \in T$, for all $x,y,z \in \mathbb{R}$: \begin{align*} f(t+f(z)+f(x)+y)&=f(t+z+f(f(x)+y)) \\ &= f(t+z+f(x+f(y))) \\ &= f(t+f(z)+x+f(y)) \end{align*}Therefore $t+f(z) \in T$ as well. Therefore all finite sums of numbers from $R$ are in $T$. Let $g(x)=f(x)-x$. Therefore whenever $t \in T$, we have $$f(t+f(x)+f(y)-g(x))=f(t+f(x)+f(y)-g(y))$$for any $x,y \in \mathbb{R}$. In particular this is true when $t=0$ or $t$ is finite sum of numbers from $R$. Choose an $a \in R$ such that $|f^{-1}(a)|$ is minimum, say equal to $n$. Let $y$ satisfy $f(y)=a$. Let $x_1,x_2, \dots x_n,x_{n+1}$ be arbitrary distinct real numbers. Choose a real number $x_0$ such that $$\sum_{i=0}^{n+1}f(x_i) -g(x_0)=x_0+ \sum_{i=1}^{n+1}f(x_i) =a$$Then from the above paragraph, the value of $f$ at all numbers of the form $\sum_{i=0}^{n+1}f(x_i)-g(x_i)$ for $1 \leq i \leq n+1$ is $a$. Therefore by the condition on $a$, for some distinct $x_i,x_j$ we must have $g(x_i)=g(x_j)$. Therefore $g$ takes at most $n$ values; say it takes the $k$ distinct values $c_1,c_2, \dots c_k$. But then, $f(x)=b$ $\implies$ $x=b-c_i$ for some $i$ $\implies$ $|f^{-1}(b)| \leq k \leq n$ for all $b \in R$. Therefore by the minimality of $n$, we must have $k=n$, and $|f^{-1}(b)|=n$ for all $b \in R$. But this is only possible if all the numbers of the form $b-c_i$ are in $f^{-1}(b)$, i.e., $f(b-c_i)=b$ for all $i$ and all $b \in R$. If $n=1$, and if we let $c_1=c$ we get the solution $$\boxed{f(x)=x+c \ \ \forall x \in \mathbb{R}}$$where $c$ is any real number. Hence from now on assume $n \geq 2$. Partition $\mathbb{R}$ into disjoint subsets $S_1,S_2, \dots S_n$ such that $x \in S_i$ $\iff$ $f(x)=x+c_i$. Clearly we have $S_i \subset R-c_i$. But, for any $b \in R$, by the above discussion we have $b-c_i \in S_i$, and so in fact $S_i=R-c_i$ for all $i$. Claim 1: $R+R \subset R$ Proof: Let $c_i$ and $c_j$ be the largest and smallest among $c_1,c_2, \dots c_n$. Clearly $c_i-c_j=c_{i'}-c_{j'}$ iff $i=i'$ and $j=j'$. Putting arbitrary $x \in S_i$ and $y \in S_j$ in the original equation gives $f(x+y+c_j)=f(x+y+c_i)$. The LHS is at most $x+y+c_j+c_i$ while the RHS is at least $x+y+c_i+c_j$, and equality holds only if $x+y+c_j \in S_i$ and $x+y+c_i \in S_j$. Thus $S_i + S_j + c_j \subset S_i$ $\implies$ $S_i+R \subset S_i$, and this implies $$R+R=S_i+c_i+R \subset S_i+c_i = R$$as required. $\blacksquare$ WLOG assume $0 \in S_1 = R-c_1$ $\implies$ $c_1 \in R$. Now we have $R+c_1 \subset R+R \subset R$, and so $R \subset R-c_1=S_1$. Thus $R$ is completely contained in one section of the partition. Claim 2: $S_1+S_1 \subset S_1$ Proof: Assume FTSOC that $S_1+S_1 \cap S_i \neq \O$ for some $i \neq 1$ $\implies$ $S_1+S_1+2c_1 \cap S_i+2c_1 \neq \O$. But, $$S_1+S_1+2c_1=R+R \subset R \subset S_1$$and $c_1 \in R$ $\implies$ $2c_1=c_1+c_1 \in R$, and so $$S_i+2c_1 \subset S_i+R=R-c_i+R \subset R-c_i=S_i$$Thus we get a contradiction because $S_1 \cap S_i = \O$. $\blacksquare$ Claim 3: For any $x \in \mathbb{R}$, there is a positive integer $m \leq n$ such that $mx \in S_1$. Proof: Assume FTSOC that none of the numbers $x,2x, \dots nx$ are in $S_1$. Thus they are in one of $S_2, \dots S_n$. So by pigeonhole principle, there is an $i \neq 1$ as well as positive integers $k_1<k_2 \leq n$ such that $k_1x,k_2x \in S_i$. Assume $(k_2-k_1)x \in S_j$, where $j \neq 1$ since $k_2-k_1$ is also a positive integer $\leq n$. Therefore $k_2x=(k_2-k_1)x+k_1x \in S_i+S_j$ $\implies$ $S_i+S_j \cap S_i \neq \O$ $\implies$ $S_i+c_i+S_j \cap S_i+c_i \neq \O$. But $S_i+c_i=R \subset S_1$, and $$S_i+c_i+S_j = R+(R-c_j) \subset R-c_j=S_j$$Thus we get a contradiction because $j \neq 1$ $\implies$ $S_1 \cap S_j = \O$. Therefore such an $m$ exists for all real numbers $x$. $\blacksquare$ Now we can finally finish the argument. Let $M=n!$. From Claims 2 and 3, we get that $Mx \in S_1$ for all reals $x$. But now choose any $y \in S_2$, then $y=M \cdot \frac{y}{M} \in S_1$, contradiction! Thus there are no solutions for $n \geq 2$.
16.06.2022 14:19
What is $f^{-1}(x)$?
16.06.2022 14:36
ZETA_in_olympiad wrote: What is $f^{-1}(x)$? It's defined in the statement of the problem. In general, if $A,B$ are sets, then $f(A)=\{f(a):a\in A\}$ and $f^{-1}(B)=\{b:f(b)\in B\}$, in particular, when $B=\{a\}$ is a singleton, it is usually written as $f^{-1}(a)$ instead of $f^{-1}(\{a\})$.
16.06.2022 14:45
GianDR wrote: ZETA_in_olympiad wrote: What is $f^{-1}(x)$? It's defined in the statement of the problem. In general, if $A,B$ are sets, then $f(A)=\{f(a):a\in A\}$ and $f^{-1}(B)=\{b:f(b)\in B\}$, in particular, when $B=\{a\}$ is a singleton, it is usually written as $f^{-1}(a)$ instead of $f^{-1}(\{a\})$. So it is a set. Sorry for not reading it correctly. I thought it'd be $1/f(x)$ but thanks.
17.06.2022 00:24
ZETA_in_olympiad wrote: So it is a set. Sorry for not reading it correctly. I thought it'd be $1/f(x)$ but thanks. I must warn you that this isn't correct. In any case it would be the image of $x$ via the inverse function of $f$, it's the same as the fact that we don't mean $1/\sin (x)$ when we write $\sin ^{-1}(x)$. If you want to talk about $1/f(x)$, you should write $(f(x))^{-1}$ (the parenthesis aren't really necessary, but they would probably help).
24.06.2023 03:35
Let $k$ be such that the number of reals $x$ such that $f(x)=k$ are maximum and equal to $l$ assume that $l>1$. let $f(a_1)=f(a_2)=f(a_3)=...=f(a_l)=k$ then $f(f(y)+a_1)=f(f(y)+a_2)= ... =f(f(y)+a_l)=f(y+k)$ (this result is obtained by putting $x=a_1$ then $x=a_2 ...$ then $x=a_l $ in the original equation) note that there are less than or equal to $l$ preimages of $f(y+k)$ and $f(y)+a_i$ are all distinct so$ y+k$ must be one of $f(y)+a_i$ $\Longrightarrow$ $f(y)-y $belongs to the set $T=${$k-a_1,k-a_2,...,k-a_l$} Claim :$J=f (x_1)+f(x_2)+f(x_3)+...f(x_n)=a_i-a_j $has no solutions for $x_i\in\mathbb{R}$ , $i$$\ne$$j$ and $n\in\mathbb{N}$ .
Now let $f(a_i-k)=a_i-k+k-a_j=a_i-a_j $now by claim 1, $ a_i $ and $a_j $ can not be distinct $\Longrightarrow$$ i=j$ and $f(a_i-k)=0$ Let $g(x)=f(x-k)$$\Longrightarrow$$g(x)-x $belongs to {$-a_1,-a_2, .. ,-a_l$} and $x=x-k$ and $y=y-k$ in the original equation gives us $ g(x+g(y))=g(y+g(x))$ . since $f(a_i-k)=0 $we have $g(a_i)=0$ Now let $P(x,y)$ be assertion of $g(x+g(y))=g(y+g(x)) $ then $P(x,a_i)$$\Longrightarrow$$$g(x)=g(a_i+g(x)) $$claim 2:$g(y)-g(x)=a_i-a_j$ has no solution for $i$$\ne$$j$
claim 2 $\Longrightarrow$$g(x+a_1)-(x+a_1) , g(x+a_2)-(x+a_2) , .. , g(x+a_l)-(x+a_l) $are all distinct for all real $x$ and equal to the set {$-a_1,-a_2, .. ,-a_l$} $g(x+a_1)-(x+a_1) + g(x+a_2)-(x+a_2) + .. +g(x+a_l)-(x+a_l) =-a_1-a_2 .. -a_l$$\Longrightarrow$ $g(x+a_1)+g(x+a_2)+ .. +g(x+a_l)=lx$ for $x={(a_2-a_1)}/l$ we have $g(x+a_1)+g(x+a_2)+ .. +g(x+a_l)=a_2-a_1$$\Longrightarrow$ $f(x+a_1-k)+f(x+a_2-k)+ .. +f(x+a_l-k)=a_2-a_1$ which is a contradiction to claim 1 this proves that our initial assumption that $l>1$ was false. This implies that $ l=1$ which implies $f$ is injective $\Longrightarrow$$f(x)+y=f(y)+x$$\Longrightarrow$$f(x)-x=c$ for some constant $c$. Hence the only solution is $f(x)=x+c$ for some $c\in\mathbb{R}$