Find all functions $f: \mathbb{N}_{0}\to \mathbb{N}_{0}$ such that for all $n\in \mathbb{N}_{0}$: \[f(m+f(n))=f(f(m))+f(n).\]
Problem
Source:
Tags: function, induction, Functional Equations
26.09.2007 02:27
At first I was surprised I got an IMO #3 (or did I?), and then I noticed that imo-official suggests it wasn't much of a number 3. Darn. Put $ m = n = 0$ in to get $ f(0) = 0$. Put $ m = 0$ in to get $ f(f(n)) = f(n)$. Now the given equation reduces to $ f(m+f(n)) = f(m)+f(n)$. We note now that $ f(n) = 0$ for all nonnegative $ n$ is a solution. Now assume it away. Therefore there exist positive integers $ a,b$ such that $ f(a) = b$. Since $ f(f(a)) = f(a)$, $ f(b) = b$. This implies that if we disregard $ f(n) = 0$, $ f$ has at least one nontrivial fixed point. Suppose $ a$ is positive and a fixed point of $ f$, i.e. $ f(a) = a$. Put $ m = n = a$ in to the equation to get $ f(2a) = 2a$. We see that induction will guarantee that $ f(ka) = ka$ for all positive integers $ k$. Let $ a$ be the smallest positive integer such that $ f(a) = a$. We now prove that if $ f(b) = b$, $ a\mid b$. First, let $ d$ be such that $ d = (a,b)$. Then there exist positive integers $ x,y$ such that $ ax-by = d$. Now put $ m = d, n = by$ in. This makes the LHS $ f(d+f(by)) = f(d+by) = f(ax) = ax$. The RHS is $ f(d)+f(by) = f(d)+by$. Setting these equal, the result is $ ax = f(d)+by$. Then $ f(d) = ax-by = d$. So $ f(d) = d$. But $ d\leq a$ and $ a$ is the minimal fixed point. Therefore $ d = a$, $ (a,b) = a$, and thus $ a$ divides $ b$. So if $ a$ is the smallest positive integer such that $ f(a) = a$, we now have that the image of $ f$ is exactly the multiples of $ a$ including $ 0$. Our (new) given equation, $ f(m+f(n)) = f(m)+f(n)$, can now be rewritten as $ f(m+ka) = f(m)+ka$ for all nonnegative $ m$ and $ k$. Additionally, $ f$ outputs only multiples of $ a$. Consider $ f(b)$ for any positive $ b$ less than $ a$. (If no such $ b$ exists, this means $ a = 1$ and we get the solution $ f(n) = n$) Set $ f(b)$ to any arbitrary multiple of $ a$, and do this for all $ 0 < b < a$. Putting $ m = b$ gives $ f(b+ka) = f(b)+ka$. This defines $ f$ for all positive integers. We check to see that all of these solutions work, no matter what multiple of $ a$ we set each $ f(b)$ to. The end answer: Either $ f(n) = 0$ for all nonnegative integers $ n$ or the following. Let $ a$ be any positive integer, and let $ x_{1}, x_{2},\ldots x_{a-1}$ be any sequence of nonnegative integers. Then we get a new solution of $ f$: $ f(0) = 0$, $ f(ka) = ka$ for all positive integers $ k$, and $ f(b+ka) = a(k+x_{b})$ for all positive integers $ k$ and positive integers $ b < a$.
24.02.2013 21:27
new solution ,post 15 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=36&t=60429&p=2943710#p2943710 i'm enough lazy to avoid reading mellowmelos's solution ,but at the first glance i saw that the solution's got its first idea_minimality of..._ anyway i hope i used something different to get the answeres...
21.05.2022 21:20
Solution