Does S contain 0 ? :

First, it is clear that $ f$ is injective. Then, note that we always have $ (x+3)^2 + 2x^2 = (x-1)^2 +2 (x+2)^2$. Back to the original equation, it follows that $ f^2(x+3) + 2f^2(x) = f^2(x-1)^2 +2f^2 (x+2)$. Let $ u_n = f^2(n)$. Thus $ u_{n+3} - 2u_{n+2} + 2u_n - u_{n-1} = 0$ for all $ n>1$. Solving this linear relation, we get that $ u_n = an^2 + bn + c + d(-1)^n$ for all $ n > 0$ for some constant $ a,b,c,d$. Moreover, from the initial equation, we have $ 2u_1 + u_5 = 3u_3$ from which we deduce that $ b = 0$. Thus, $ u_n = an^2 + c + d(-1)^n$ and is the square of an integer. It is a classical result that $ a$ is a square of an integer and $ c=d=0$. Thus, for some positive integer $ k$, we have $ f(n) = kn$ for all $ n>0$. Back to the initial equation, we deduce that $ f(n) = n$ for all $ n>0$, which is clearly a solution. Pierre.

Quite nice !

I think it is quite better than the official solution. Good work pbornsztein, you increased my respect to the problem

Ahiles wrote: Denote by $ S$ the set of all positive integers. Find all functions $ f: S \rightarrow S$ such that $ f \bigg(f^2(m) + 2f^2(n)\bigg) = m^2 + 2 n^2$ for all $ m,n \in S$. Bulgaria. First let $ m=n=1$ to get $$f(3f(1)^2)=3\, .$$Then $ (m+2n)^2+2(m-n)^2=(m-2n)^2+2(m+n)^2$ and injectivity gives \begin{align*} f(m+2n)^2+2f(|m-n|)^2&=f(|m-2n|)^2+2f(m+n)^2\, \end{align*}From now on we will use only this equation. Plug $ m=f(1)^2$ and $ n=2f(1)^2$ to get $$f(5f(1)^2)^2+2f(f(1)^2)^2=3f(3f(1)^2)^2=27\, .$$By solving equation $ a^2+2b^2=27$ in positive integers we get the following cases Case 1: If $ f(5f(1)^2)=3=f(f(1)^2) $, then by injectivity $$5f(1)^2=f(1)^2\Longrightarrow f(1)=0$$which is a contradiction. Case 2: If $ f(5f(1)^2)=5$ and $ f(f(1)^2)=1$, then by letting $ m=3f(1)^2$ and $ n=f(1)^2$ we get \begin{align*} f(5f(1)^2)^2+2f(2f(1)^2)^2&=f(f(1)^2)^2+2f(4f(1)^2)^2\\ 12 + f(2f(1)^2)^2 &= f(4f(1)^2)^2\, . \end{align*}So, $ f(2f(1)^2)=2$ and $ f(4f(1)^2)=4$ Now, use induction to prove that $ f(kf(1)^2)=k$ for all $k \in S$. $ (1)$ For $ k=1,2,3,4,5$ it was shown above. $ (2)$ Assume the claim holds up to some $k > 5$. $ (3)$ By taking $ m=(k-2)f(1)^2$ and $ n=f(1)^2$ we get \begin{align*} f(kf(1)^2)^2+2f((k-3)f(1)^2)^2&=f((k-4)f(1)^2)^2+2f((k-1)f(1)^2)^2\\ f(kf(1)^2)^2+2(k-3)^2&=(k-4)^2+2(k-1)^2\\ f(kf(1)^2)&=k\, . \end{align*}This completes induction. Since $ f(1)$ is a positive integer $$ f(f(1)f(1)^2)=f(1) \Longrightarrow f(1)=1\,.$$So $ f(k)=k$ for all $k\in S$. Hope all calculations are correct...

cefer wrote: Hope all calculations are correct... I think, there is no mistake in official solution

YOGRRR wrote: cefer wrote: Hope all calculations are correct... I think, there is no mistake in official solution Hmm... How can I know this is same as official one ? Anyway, thanks a lot.

pbornsztein , how to prove $ a$ is a perfect square , $ d = c = 0$ ?

Well it's not so difficult: you want $ an^2+c+d(-1)^n$ to be a perfect square for all natural $ n$. It's obvious that $ a$ is nonnegative (we assume it's positive because $ a=0$ gives as f to be a constant function which is not a solution). Now we shall be interested what is happening only over the even $ n$. Let $ c+d=b$. So $ an^2+b$ is a perfect square for all even $ n$. Let $ n$ is even and $ an^2+b=p^2$, $ a(2n)^2+b=4an^2+b=q^2$. Then $ 4an^2+4b=(2p)^2$. If $ b$ is not equal 0 then we have 2 cases. 1) $ b>0$ and we get $ 3b=(2p)^2-q^2$. Since $ b>0$ we get $ 2p>q$ so $ 3b>=(q+1)^2-q^2=2q+1$. Now it's clear that $ q>n$, so for large $ n$ we get a contadiction. 2) $ b<0$ - in the same way for large $ n$ we get contradiction. Thus we must have $ b=0$ and so $ a$ must be a square of integer. Since a is a square and $ c+d=0$ it is now easy to get $ c=d=0$

I think it is the best problem of BMO-2009 I like it but you can get 1 point from finding f is surjective I think it is very simple

ufuk wrote: I think it is the best problem of BMO-2009 I like it but you can get 1 point from finding f is surjective I think it is very simple I think you mean injective

yes,thank you

Proof of pbornsztein's result can be found here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=591&t=290821

pbornsztein wrote: Let $ u_n = f^2(n)$. Thus $ u_{n+3} - 2u_{n+2} + 2u_n - u_{n-1} = 0$ for all $ n>1$. Solving this linear relation, we get that $ u_n = an^2 + bn + c + d(-1)^n$ for all $ n > 0$ for some constant $ a,b,c,d$. why these constants exist? in specially $ d $ ?

pbornsztein wrote: First, it is clear that $ f$ is injective. Then, note that we always have $ (x+3)^2 + 2x^2 = (x-1)^2 +2 (x+2)^2$. Back to the original equation, it follows that $ f^2(x+3) + 2f^2(x) = f^2(x-1)^2 +2f^2 (x+2)$. Let $ u_n = f^2(n)$. Thus $ u_{n+3} - 2u_{n+2} + 2u_n - u_{n-1} = 0$ for all $ n>1$. Solving this linear relation, we get that $ u_n = an^2 + bn + c + d(-1)^n$ for all $ n > 0$ for some constant $ a,b,c,d$. Moreover, from the initial equation, we have $ 2u_1 + u_5 = 3u_3$ from which we deduce that $ b = 0$. Thus, $ u_n = an^2 + c + d(-1)^n$ and is the square of an integer. It is a classical result that $ a$ is a square of an integer and $ c=d=0$. Thus, for some positive integer $ k$, we have $ f(n) = kn$ for all $ n>0$. Back to the initial equation, we deduce that $ f(n) = n$ for all $ n>0$, which is clearly a solution. Pierre. Sorry but how to solve this linear relation for 4 elements?

Very nice solution: Let $A(m,n)$ be assertion of $ f (f^2(m) + 2f^2(n)) = m^2 + 2 n^2$. First thing is to show that $f$ is injective. Assume $f(a)=f(b)$. From $A(m,a)$,$A(m,b)$ it holds that $a=b$ that is $f $is injective. Assume $f(1)=a$. $A(1,1)$ implies $f(3a^2)=3$. If we look for numbers $m_1,m_2,n_1,n_2$ such that $m_1^2+2n_1^2=m_2^2+2n_2^2$ we see that $(5,1,3,3), (1,4,5,2)$ are such numbers. Now $A(5a^2,1a^2)$ ,$A(3a^2,3a^2)$ , $A(1a^2,4a^2)$ and $A(5a^2,2a^2)$ imply that $f(2a^2)=2,f(5a^2)=5,f(a^2)=1,f(4a^2)=4$(basic computation ) Now since $x^2+2(x+3)^2=(x+4)^2+2(x+1)^2$ assuming that for $n\le x+4$ ,$f(na^2)=n$ it implies that from $A(xa^2,2(x+3)a^2)$,$A((x+4)a^2,(x+1)a^2)$ that $f((x+4)a^2)=x+4$. So we have $f(na^2)=n$ but now plugging in $n=a$ we have $f(a^3)=a=f(1)$ $\implies a=1$ $\implies$ $\boxed{f(n)=n}$ which indeed is solution.

pbornsztein wrote: First, it is clear that $ f$ is injective. Then, note that we always have $ (x+3)^2 + 2x^2 = (x-1)^2 +2 (x+2)^2$. Back to the original equation, it follows that $ f^2(x+3) + 2f^2(x) = f^2(x-1)^2 +2f^2 (x+2)$. Let $ u_n = f^2(n)$. Thus $ u_{n+3} - 2u_{n+2} + 2u_n - u_{n-1} = 0$ for all $ n>1$. Solving this linear relation, we get that $ u_n = an^2 + bn + c + d(-1)^n$ for all $ n > 0$ for some constant $ a,b,c,d$. Moreover, from the initial equation, we have $ 2u_1 + u_5 = 3u_3$ from which we deduce that $ b = 0$. Thus, $ u_n = an^2 + c + d(-1)^n$ and is the square of an integer. It is a classical result that $ a$ is a square of an integer and $ c=d=0$. Thus, for some positive integer $ k$, we have $ f(n) = kn$ for all $ n>0$. Back to the initial equation, we deduce that $ f(n) = n$ for all $ n>0$, which is clearly a solution. Pierre. Sorry for reviving this , but how did he find the linear relation ( the general term of the sequence )

Clearly, $f$ is injective, so $f(a)^2+2f(b)^2 = f(c)^2+2f(d)^2$ whenever $a^2+2b^2=c^2+2d^2$. Using the identities \[(2k+1)^2-(2k-1)^2=8k=2((k+1)^2-(k-1)^2)\]\[(2k+2)^2-(2k-2)^2=16k=2((2k+1)^2-(2k-1)^2)\]as well as the small quadruplets $(a,b,c,d) = (5, 1, 3, 3), (5, 2, 1, 4)$, by induction, we derive: \[f(2n)^2 = \frac{n^2-1}{2}f(3)^2+f(2)^2-\frac{n^2-1}{2}f(1)^2 \quad\forall n\geq 2\]\[f(2n+1)^2 = \frac{n(n-1)}{2} f(3)^2 - \frac{n(n-1)-2}{2}f(1)^2\quad \forall n\geq 2\]It's also straightforward to get that $f$ preserves the parity of the input (by the above equations parametrized by $k$), so we can set \[\frac{-f(3)^2+2f(2)^2+f(1)^2}{2}=C\in\mathbb{Z}, \quad \frac{f(3)^2-f(1)^2}{2} = D\in\mathbb{Z}_{\neq 0}\]whence $f(2n)^2 = Dn^2+C$ is a perfect square for all $n\in\mathbb{N}_{\geq 2}$ and $D$ is nonzero as $f(1)^2 \neq f(3)^2$ due to the injectivity. If $C$ is not a perfect square, plugging in $n$ to be a multiple of $|C|$ derives a contradiction, hence $C = \varepsilon c^2$ for $\varepsilon=\pm 1$. If $C\neq 0$, plugging in $n=m|C|$ shows that $CDm^2+\varepsilon$ is a perfect square for infinitely many consecutive integers $m$, which is impossible as $m$ must be a solution to the Pell equation $X^2 - CDY^2 = \varepsilon$, but these can't be consecutive. Therefore $C=0$ and so $f(3)^2 = 2f(2)^2+f(1)^2$, which rewrites the expression for $f(2n)^2$ to $n^2f(2)^2$. Plugging in $(m, n) = (2m, 2n)$ in the original FE yields that $f(2)=2$ as we can open all brackets. As the formula for $f(2n+1)^2$ becomes $f(1)^2+n(n-1)f(2)^2=4n^2-4n+f(1)^2$, this must be a perfect square for all $n\geq 2$, which may occur only if it is $(2n-1)^2$. Hence $f(1) = 1$, and from here we can trace back that $f(n) = n$ for all $n\in \mathbb{N}$, which clearly works.