Its not hard to guess that $f(x)=x$ works well. Actually, I just don't know if it's the only possible solution for that. It's quite reasonable to observe that an aplication of f sends 0 into itself. And by taking m=0, we opberve that $f(f(n))=f(n), \forall n$ So i can garantee that there are more fixed points...don't know if that's a nice observation, because I can't conclude much about...but i wanted to discuss about this problem

There are definitely more solutions. I don't have the time to write a detailed solution, and it's not that hard anyway, but I believe the solutions can be described like this: Take some $r\in\mathbb N_0$, let $f$ map $1,2,\ldots,r-1$ onto some multiples of $r$ arbitrarily, put $f(kr)=kr,\ \forall k\in\mathbb N_0$, and extend the function to the other naturals by setting $f(u+r)=f(u)+r,\ \forall u\in\mathbb N_0$.

Kalva Solution: Setting $m = n = 0$, the given relation becomes: $f(f(0)) = f(f(0)) + f(0)$. Hence f(0) = 0. Hence also $f(f(0)) = 0$. Setting $m = 0$, now gives $f(f(n)) = f(n)$, so we may write the original relation as $f(m + f(n)) = f(m) + f(n)$. So $f(n)$ is a fixed point. Let $k$ be the smallest non-zero fixed point. If $k$ does not exist, then $f(n)$ is zero for all $n$, which is a possible solution. If $k$ does exist, then an easy induction shows that $f(qk) = qk$ for all non-negative integers $q$. Now if $n$ is another fixed point, write $n = kq + r$, with $0$ ≤ $r$ < $k$. Then $f(n) = f(r + f(kq)) = f(r) + f(kq) = kq + f(r)$. Hence $f(r) = r$, so $r$ must be zero. Hence the fixed points are precisely the multiples of $k$. But $f(n)$ is a fixed point for any $n$, so $f(n)$ is a multiple of $k$ for any $n$. Let us take $n_1, n_2, ... , n_{k-1}$ to be arbitrary non-negative integers and set $n_0 = 0$. Then the most general function satisfying the conditions we have established so far is: $f(qk + r) = qk + n_rk$ for $0$ ≤$r$ < $k$. We can check that this satisfies the functional equation. Let $m = ak + r$, $n = bk + s$, with $0$ ≤ $r, s$ < $k$. Then $f(f(m)) = f(m) = ak + n_rk$, and $f(n) = bk + n_sk$, so $f(m + f(n)) = ak + bk + n_rk + n_sk$, and $f(f(m)) + f(n) = ak + bk + n_rk + n_sk$. So this is a solution and hence the most general solution.

I'm not sure about this... but it seems right.

Philip_Leszczynski wrote: I'm not sure about this... but it seems right.

wrong solution.

Philip_Leszczynski wrote: But then $f(f(x)) = cf(x) = c^2x > cx$. Contradiction if $c \ge 2$ (since $f(f(x)) = f(x)$) So $c=0,1$. But if $c=1$, then $f(x)=x$, and we obviously have a contradiction in the original. So $c=0$, and $f(x)=0$ for all x. This part here seems very strange to me... First because you weren't so clear about your contradiction [even though you didn't assume anything to contradict!]...second because $f(x)=x, \forall x\in \mathbb{N}_0$ works very well =]

e.lopes wrote: We can check that this satisfies the functional equation. Let $m = ak + r$, $n = bk + s$, with $0$ ≤ $r, s$ < $k$. Then $f(f(m)) = f(m) = ak + n_rk$, and $f(n) = bk + n_sk$, so $f(m + f(n)) = ak + bk + n_rk + n_sk$, and $f(f(m)) + f(n) = ak + bk + n_rk + n_sk$. So this is a solution and hence the most general solution. When you are verifying, I think you should not make the assumption $f(f(m))=f(m)$. If $f(qk+r)=qk + n_r k$, how do you prove that $f(f(m))=f(m)$ ? Suppose otherwise that $f(f(m))=f(m)$. Then $qk+n_r k = f(qk+r) = f(f(qk+r))=f(qk+n_r k)=qk + n_{n_r k}k$, so $n_r = n_{n_r k}$ : but why should they be equal ?

Can't we conclude from f(f(n))=f(n), that f(n)=n.

quantumbyte wrote: Can't we conclude from f(f(n))=f(n), that f(n)=n. Actually we can, but first we must show that $f$ is injective.

Can you explain to me how we could do that?

I don't think so. I have written this statement for the general case.

I hope I am not reviving anything.

This solution does not work.

Here's a new solution(i guess) by me : suppose function is not constant(or else f=0) : it is not hard to get f(0)=0, f(kf(n))=kf(n) (*),f(f(n))=f(n) (**), so if there exists some natural (or zero) i so that f(i)=1,then we will get f(k)=k by (*), suppose the least natural number which the function could produce is p, then by (*) we have f(kp)=kp, where k is a natural number, it's not hard to find that f(m+f(n))=f(f(m)) + f(n) is equal to f(m+f(n))=f(m)+f(n) by (**),plugging m=i<p,n=kp , we will get f(kp+i)=kp +f(i) ,so : set n=kp+i,i<p, f(f(n)=f(n) so f(kp+f(i))=kp+f(i),by the assumption of the minimality of function, we get f(i)=sp+j ,0<j<p so f(kp+sp+j)=kp+sp+f(j)=kp+sp+j so f(j)=j, contradiction with minimality,so in this case we get the least minimality is equal to 1 and so f(k)=k for all naturals,and it's Done. ..... if j=0,then f(i)=sp for some arbitrary natural(or zero) s....the rest is Done. typos fixed.

Is it true? Let $m=n=0$. Then $f(0+f(0))=f(f(0))=f(f(0))+f(0)$. Then $f(0)=0$. Then put in $m=0$. We get $f(f(n))=f(f(0))+f(n)=f(n). Then $f(m+f(n))=f(m)+f(n). Assume that $a, b, c$ are arbitrary integer nonnegative numbers. Then consider $f(a+b+f(c))$. Using condition we get: 1) $f(a+b+f(c))=f(a)+f(b+f(c))=f(a)+f(b)+f(c)$ 2) $f(a+b+f(c))=f(a+b)+f(c)$. So $f(a+b)=f(a)+f(b)$. It's well-known Cauchy's functional equation. As we have integer numbers, $f(x)=kx$ (k is an arbitrary nonngative number). As $f(f(n))=f(n)$, $k^2n=kn$, so $k=0$ or $k=1$. So the only solvings are $f(x)=x$ and $f(x)=0$

you can only apply Cauchy's function if and only if f is continouse. so you're not done.

MBGO wrote: you can only apply Cauchy's function if and only if f is continouse. so you're not done. Actually, here it's ok because it's on the integers. But you're right, McItran is not done. His issue is here: McItran wrote: 1) $f(a+b+f(c))=f(a)+f(b+f(c))$ You cannot just take $a$ outside into its own function. You need justification for that, and since you have none, you are wrong. You can also check that you are wrong because $f(x)=x$ if $x$ is even and $f(x)=x-1$ if $x$ is odd also works.

@tenniskidperson3 : would you please check the end part of my solution? where i get in the last line : "f(i)=sp"?

i think i have a pretty idea why don't we generalize the exercise to be more free with it thing like working in R in fact it will be more easy to deal with the equation if we prove that f(1)=1 we re done

MBGO wrote: we will get f(kp+i)=kp +i False, we will get $f(kp+i)=kp+f(i)$. MBGO wrote: we get f(i)=sp+j ,0<j<p False again, we can have $j=0$. MBGO wrote: so f(j)=j, contradiction with minimality ... unless $j=0$ for all integers.

first one was just a typo,EDITED, second one i just devide the solution in two cases,the case where 0<j and j=0...i the only thing i doubt on it is when f(i)=sp,where i<p

OK, I didn't understand what you were writing. It looks OK to me now.

tenniskidperson3 wrote: MBGO wrote: you can only apply Cauchy's function if and only if f is continouse. so you're not done. Actually, here it's ok because it's on the integers. But you're right, McItran is not done. His issue is here: McItran wrote: 1) $f(a+b+f(c))=f(a)+f(b+f(c))$ You cannot just take $a$ outside into its own function. You need justification for that, and since you have none, you are wrong. You can also check that you are wrong because $f(x)=x$ if $x$ is even and $f(x)=x-1$ if $x$ is odd also works. Oh, I'm sorry

Let $\Omega = \text{Im} (f) $. Throughout my solution, $a,b$ will denote elements of this set. Notice that $f(m+a)=f(f(m))+a$, this is the statement. Then $f(a+b)=f(a)+b=f(b)+a$ and therefore $f(a)-a$ is constant $\forall a \in \Omega$. Also $a+c=f(a)=f(0+a)=f(f(0))+a=f(0)+a+c$ and so $f(0)=0$. Then if $a=0, c=0$ and so $f(a)=a \forall a \in \Omega$. Notice also $f(m+a)=f(m)+a$. Notice that if $a,b \in \Omega$ then $f(a+b)=a+b$ so $\Omega$ is additive and if $b > a$ then $b=f(b)=f((b-a)+a)=f(b-a)+a$ then $\Omega$ is "subtractive". We obtain that $\Omega=\{0\}$ or the set of multiples of a positive integer $d$. In the first case, $f=0$ doesn't work. In the other case, we obtain $f(m+kd)=f(m)+kd$ and so the solution is: Let $d$ be any positive integer and choose any $a_1,...,a_{d-1} \in \mathbb{N}_0$. Then $f(kd+i) = kd+a_i$ for $k \in \mathbb{N}_0$ and $1 \le i \le d-1$ and $f(kd)=kd$.

Let $g$ be an arbitrary positive integer and let $a_1,a_2,\cdots a_{g-1}$ be an arbitrary sequence of nonnegative integers, with $a_0=0$. Any solution in the form \[ f(pg+r)=pg+a_r \]for $0\le r<g$ can easily be shown to be valid. Now we show that any possible function is in this form. Indeed, $P(0,0)$ implies $f(0)=0$, and $P(0,n)$ implies $f(f(n))=f(n)$. Then \[ f(m+f(n))=f(m)+f(n) \]so $f$ is periodic modulo any integer in its range. Let $g>0$ be the gcd of the range of $f$ (noting that the solution $f(x)=0$ identically has been accounted for in the solution set, and so we may assume otherwise). Then some linear combination of elements of the range of $f$ form any multiple of $g$, so in particular \[ f(m+kg)=f(m)+kg \]for any $m,k$. This implies that $f$ is in the above form.

Hmm... quite a nice yet nasty problem- the amount of time I tried to prove $f(n)=n$ is ridiculous. First, we get over with the standard stuff- $P(0,0): f(f(0))=f(0)+f(f(0))=>f(0)=0$. $P(0,n): f(f(n))=f(n)$. Now, it becomes quite hard to play with the function too much, and after you get $f(m+f(n))=f(m)+f(n)$, the only way I found to move forward is noticing that $P(n,n):f(2f(n))=2f(n)$, $P(2f(n),n):f(3f(n))=3f(n)$, and so on- from here we can easily prove by induction $f(tf(n))=tf(n)$ for any non-negative integer $t$. Also notice that $P(m,tf(n)): f(m+tf(n))=f(m)+tf(n)$. Funnily enough, we're almost done... just choose the smallest non-negative fixed point(if there exists one) $n_0$ such that $f(n_0)=n_0$ - thus $f(tn_0 +m)=f(m)+tn_0$. Now let's consider other values of $f(n)$ - let one of them be $p => f(p)=p$. Say $kn \leq p <(k+1)n$ for some positive integer $k$- thus $P(p-kn_0,kn_0)$ gives us $f(p)=f(p-kn_0)+kn_0=>f(p-kn_0)=p-kn_0$-thus $ p-kn_0$ is a fixed point, but we assumed $n_0$ to be the smallest such number! Hence $p=kn_0$ for all $p$, or $f(n)=kn_0$ for all $n$ for some integer $k$... letting $n=an_0+b$, $0 \leq b \leq n_0-1$, we get $n_0 \mid an_0 +f(b)=>n_0 \mid f(b)$. Here I couldn't find any other restriction on $f(b)$, and I spent more time than I'd like to admit trying to prove $n_0=1$ ... anyways it turns out you don't need any more restrictions on $f(b)$ or $n_0$ - hence our general solution becomes $f(an_0+b)=an_0 + f(b), 1 \leq b \leq n_0 -1, n_0 \mid f(b)$, and it's easy to verify this works. It really is quite a nice problem, and it could be quite deceiving as such a general solution is usually... unlikely (and very frustrating if you're on the wrong track), but still- an IMO P3? Most of the steps are actually quite natural, and the substitutions and even the fixed point method are also quite well known- maybe because it's a pre-2000 question, so functional equations weren't that common, I suppose.

The answer is all functions $f$ such that if $a$ is the greatest common factor of the range of $f$, then $f(aq+r)=aq+f(r)$ whenever $r<a$. It is easy to check that this works: if $m=aq_1+r_1$ and $n=aq_2+r_2$, where $r_1<a$ and $r_2<a$, then \begin{align*} f(m+f(n))&=f(aq_1+r_1+f(aq_2+r_2))\\ &=aq_1+f(r_1+aq_2+f(r_2))\\ &=aq_1+aq_2+f(r_1)+f(r_2)\\ &=f(aq_1+f(r_1))+f(aq_2+r_2)\\ &=f(f(m))+f(n). \end{align*}Now we prove this describes all solutions to the functional equation. Let $P(m,n)$ denote the assertion. First, $P(0,0)$ gives $f(f(0))=f(f(0))+f(0)$, so $f(0)=0$. Then $P(m,0)$ gives $f(m)=f(f(m))$. Hence the functional equation rewrites as \[f(m+f(n))=f(m)+f(n),\]so $f$ is periodic modulo every element of the range of $f$. The greatest common factor $a$ of the range of $f$ is expressible as a linear combination of the range of $f$, so $f$ is also periodic modulo $a$. This completes the proof.

The answer is $f(x)=a\left\lfloor\frac xa\right\rfloor+g\left(x-a\left\lfloor\frac xa\right\rfloor\right)$ for some $a\in S$, where $g:\{0,1,\ldots,a-1\}\to\mathbb N$ satisfies $g(0)=0$. It's easy (but not trivial) to see that these work. To see that these are all of the solutions: $P(0,0)\Rightarrow f(0)=0$ $P(x,0)\Rightarrow f(f(x))=f(x)$ $P(m,n)\Rightarrow f(m+f(n))=f(m)+f(n)$

The only functions are of the form $$f(qd+r) = qd + a_rd,$$where $q$ ranges over all nonnegative integers $0 \leq r<d$, $a_i$ is an arbitrary sequence of nonnegative integers for $1 \leq i < d$ and $a_0=0$, and $d$ is a fixed nonnegative integer constant. First, we verify that these functions do indeed work. Let $m = q_0d+r_0$ and $n = q_1d+r_1$, such that $$f(m+f(n)) = f(q_0d+r_0+q_1d+a_{r_1}d) = (a_{r_1}+q_1+q_0 + a_{r_0})d,$$and $$f(f(m)) + f(n) = f(q_0d+a_{r_0}d)+q_1d+a_{r_1}d = (a_{r_1}+q_1+q_0+a_{r_0})d,$$so both sides are indeed equal. Now we show these are the only such functions. Claim. $f(0) = 0$. Simply letting $m=n=0$ suffices. $\blacksquare$ Claim. $f(f(n)) = f(n)$ for all nonnegative $n$. Let $m=0$ and use the first claim. $\blacksquare$ In particular, let $d$ be the smallest number in the range of $f$. Then by the second claim, $f(d) = d$. It follows that $$f(m+d) = f(m+f(d)) = f(f(m)) + f(d) = f(m) + d.$$Thus, the values of $f(x)$ for $x \equiv i \pmod d$ for every $0 \leq i < d$ form an arithmetic sequence, and in particular $f(kd) = kd$ for any positive integer $k$. This yields the desired class of functions.

$P(0,0)\implies f(0)=0\implies f(f(n))=f(n),$ which is a fixed point. $P(x,y)\implies f(m+f(n))=f(m)+f(n).$ It's easy to see $\boxed{f\equiv 0},$ is a working solution. Suppose $f(x)\neq 0$ for some $x\in \mathbb{N}.$ Let $p$ be the least fixed point of $f.$ It follows, $2f(p)=f(p+f(p))=f(2p).$ By induction, $f(np)=np \forall n\in \mathbb{N}_0.$ Case 1: $p=1.$ Then $\boxed{f(x)=x}$ for some $x$, which is indeed a fitting solution. Case 2: $p>1.$ Let $q$ be any fixed point of $f.$ Then, $q=cp+a,$ where $c\in \mathbb{N}_0, 0\leq a<p \implies cp+a=cp+f(a) \implies a=0.$ Thus $a=cp.$ Notice $f(f(u))=f(u) \implies f(u)=pn_u \forall u, 0\leq u <b,$ where $n_u$ is positive integer and $n_0=0.$ If $n=cp+u,$ then $f(u)=(c+n_u)p.$ It can also be noticed that for any $p>1, n_0=0$ and $n_1,n_2,\dots n_p-1\in \mathbb{N}_0$ the function $\boxed{f(n)=([\frac{n}{p}] +n_u)p},$ is yet another working solution. And we are done!

First, letting $m=n=0$, we obtain that $f(0)=0$. Letting $n=0$ only, we have that $f(f(n))=f(n)$. Let $P(x,y)$ denote the reduced assertion that $f(m+f(n)) = f(m)+f(n)$. Note that, for any $m,n$ with $f(m)\geq f(n)$, \begin{align*}P(f(m)-f(n),n)&\implies f(f(m)-f(n)+f(n))=f(f(m)-f(n))+f(n)\\ &\implies f(f(m)-f(n)) = f(m)-f(n) = f(f(m))-f(f(n)).\qquad (\clubsuit) \end{align*}For $P(f(m), n)$, we obtain $f(f(m)+f(n)) = f(f(m))+f(n) = f(m)+f(n) \quad (\spadesuit)$. Let $k$ be the smallest nonzero value in the image of $f$, and suppose that $f(N)=k$. Note that $f(f(N))=f(N) = k\implies f(k)=k$. We'll first show that $f(nk)=nk$ by induction: it suffices to show that $f(\alpha_n)=nk$ for some $\alpha_n$, since computing $nk=f(\alpha_n)=f(f(\alpha_n))=f(nk)$ would finish. We already have $f(k)=k$. Also, we have that $$(\spadesuit)\implies f(nk+k)=f(f(\alpha_n)+f(k))=f(\alpha_n)+f(k)=nk+k=(n+1)k,$$which shows what we want. Claim. $k$ divides every value $f(n)$. Proof. Suppose that there is a value $n'$ such that $k\nmid f(n')$. Then, use relation $(\clubsuit)$ repeatedly in the way: $k\nmid f(n')\implies k\nmid f(n')-ka$ and $$f(n')-ka= f(n')-f(ka)=f(f(n')-f(ka))=f(f(n')-ka)\quad\forall a \text{ s.t. }ka\leq f(n')$$Taking the largest possible $a$, we would get a nonzero value $f(n')-ka$ that is mapped to itself, but $f(n')-ka<k$ by construction, contradicting the minimality of $k$. Note that we have $f(m+ak) = f(m+f(ak))=f(m)+f(ak) = f(m)+ak$ for all $m$ and $a$, so defining $f$ on the integers $1$ to $k-1$ uniquely determines $f$. Indeed, we can show that such $f$ work as long as $k$ divides each value: $$f(m+f(n)) = f\left(m+k\cdot \frac{f(n)}{k}\right) = f(m)+k\cdot \frac{f(n)}{k} = f\left(k\cdot \frac{f(m)}{k}\right)+f(n) = f(f(m))+f(n).$$