Solved with rama1728 based on the progress I made during the contest.

I lost my brain functions during the contest to solve this

suppose that $f(m) = f(m') = t$ and $m' > m$ There exists infinite many $n$ that $n+t$ is square so if $ f$ is not bounded $m' - m$ is greater than infinity so $f$ is bounded(for example less than $c$) now take an integer $a$ there exists infinity many $n$ that $f(a^2 + 1) + n$ is square but less than $a^2 + 1 + c$ now you can take $a$ such that $2a > c$, construction.

Fatemeh06 wrote: suppose that $f(m) = f(m') = t$ and $m' > m$ There exists infinite many $n$ that $n+t$ is square so if $ f$ is not bounded $m' - m$ is greater than infinity so $f$ is bounded(for example less than $c$) now take an integer $a$ there exists infinity many $n$ that $f(a^2 + 1) + n$ is square but less than $a^2 + 1 + c$ now you can take $a$ such that $2a > c$, construction. Uh I am not sure how you'd imply $f$ bounded because not all $n$ satisfy $n+t$ being a square, so only those $n$ for which $n+t$ is a square satisfy $f(n)<c$, so your proof fails.

rama1728 wrote: Fatemeh06 wrote: suppose that $f(m) = f(m') = t$ and $m' > m$ There exists infinite many $n$ that $n+t$ is square so if $ f$ is not bounded $m' - m$ is greater than infinity so $f$ is bounded(for example less than $c$) now take an integer $a$ there exists infinity many $n$ that $f(a^2 + 1) + n$ is square but less than $a^2 + 1 + c$ now you can take $a$ such that $2a > c$, construction. Uh I am not sure how you'd imply $f$ bounded because not all $n$ satisfy $n+t$ being a square, so only those $n$ for which $n+t$ is a square satisfy $f(n)<c$, so your proof fails. I don't understand can you explain more? There are infinity n that n + t is square. Take these n: f(n) + m = X^2 f(n) + m' = (X+ Y_{n})^2 m'- m >= 2Y_{n} +1 If f is not bounded so Y_{n} is not bounded so m' - m is infinity.

@above I mean that your statements do NOT imply $f$ bounded, i.e. your statements on why $f$ must be bounded are false. Why $Y_n$ being bounded affect the boundedness of $f$? Just because infinitely many $n$ satisfy that $f(n)<c$ does not imply that all $n$ satisfy that.

Cool and Fun problem! Since my solution is more or less same as #2, I will include motivation. The key idea as other FEs of this form is to prove if $f$ is not injective then it is bounded after which it is quite easy to get contradiction. We make some simple observations about perfect squares in general: 1. The numbers which can not be written as difference of squares are precisely of the form $4k+2$ 2. Each number can be written as difference of squares in finitely many ways. 3. $2k+1 = (k+1)^2-k^2$ and $4(t)=(t+1)^2-(t-1)^2$ 4. Perfect squares are $0,1$ mod $4$ $\qquad$ Assume that $f(a)=f(b)=c$ for some distinct $a,b$, notice that by $P(a,n^2-c);P(b,n^2-c)$ we find that $f(n^2-c)+a,b$ are perfect squares, now by observation 2, we find that $f(n^2-c)$ is bounded, hence it attains a value infinitely many times., Let's call this number $d$, and call the numbers attaining this value $a_i$, then $P(a_i,n^2-d)$ gives us $f(n^2-d)+a_i$ is perfect square for all $i$, however choosing large values of $i$, we see that we must have $f(n^2-d)=c$, repeating same arguement $f(n^2-c)=d$ . Now notice by observation 1 and 3, $2k+1 = (k+1)^2-k^2$ and $4(t)=(t+1)^2-(t-1)^2$, implying $f(x) \geq c + 4\sqrt{c} + 4$ and $f(x) \neq c+2 \quad (\mod 4)$ (if not of this form it implies $f$ is bounded). Now if $x \equiv -(c,c-1)$, we claim $f$ is bounded, indeed fix such a $x$, then for all $k > \sqrt{f(x)}$, we have $f(k^2-f(x))+x \equiv 0,1 (\mod 4)$, so $f(t^2-f(x)) $ is bounded because of previous argument, let's say $Im(f)$ for $x \equiv -(c,c-1) (\mod 4)$consists of ${b_1,b_2 \cdots b_k}$, so we have $f(x^2-b_i)=a_i$ implying $f(x^2-a_i)=b_i$ for large x. Now take $x$ of form $4P^2+m$ where $m \equiv -c$, this readily yields a contradiction due to size. $\qquad$ Remark: This is a very nice problem, which requires (only) blend of basic observations and size in nt, making it one of my favorites.

My solution during the contest: Let $f(x_1)=f(x_2)=l)$, with $x_1<x_2$ and again let $P(x;y)$ be the assertion. Also, if I further consider things of the form $f(m^2-n)$ I only consider them for natural values of the input. $P(x_1;a^2-l) \Rightarrow f(a^2-l)+x_1$ is a perfect square$= m_1^2$. $P(x_2;a^2-l) \Rightarrow f(a^2-l)+x_2$ is a perfect square$= m_2^2$. Thus $x_2-x_1=m_2^2-m_1^2 \ge 2m_2-1$, thus $f(a^2-l)$ is bounded for any $a>\sqrt{l}$. Take a number $l_1$ such that $f(a_i^2-l)=1$ for infinitely many values of $a_i$'s. $P(a_i^2-l; x^2-l_1) \Rightarrow a_i^2+f(x^2-l_1)-l$ is a perfect square for arbitrarily large $a_i$ meaning $f(x^2-l_1)$ is equal to $l$ for any $x>\sqrt{l}$. And now taking $P(x^2-l; y^2-l_1) $ by the same argument gives us that $f(x^2-l)=l_1$ for any $x>\sqrt{l_1}$. Claim: There is a finite number of $c_i$'s such that $\exists \; h_i, g_i \in \mathbb{N}$ such that $f(g_i)=f(h_i)=c_i$. Proof: Assume otherwise, and say $m>>n$ means $m>2024^{2024^n}$. Take $c_1>>c_2>>c_3>>c_4>>c_5$. By Pigeonhole, there exist two of them which are congruent $\mod 4$, let them be $c_i$ and $c_j$. Consider $d_i$ such that $f(x^2-c_i)=d_i$ and note that $c_i-c_j=(\frac{c_i-c_j}{4}+1)^2-(\frac{c_i-c_j}{4}-1)^2$. And let $\frac{c_i-c_j}{4}+1=a$ and $\frac{c_i-c_j}{4}-1=b$ we have that $d_i=f(a^2-c_i)=f(b^2-c_j)=d_j$. (and by the conditions $a^2>c_i$ and $b^2>c_j$). Thus $d_i=d_j$, but $c_i=f(x^2-d_i)=f(x^2-d_j)=c_j$, a contradiction. Now consider the set of finite cardinality of numbers $x_i$ such that $x_i$ is in the image of $f$ at least twice, and tha it's involutive maping, the set of numbers $y_i$ such that $f(a^2-x_i)=y_i$. I will also prove that $f(m)=x_i$ implies $m$ being of the form $a^2-y_i$. This is a straightforward results of $P(m; x^2-x_i$. Even if the last result is not that complex it is very useful, in particular it gives us that the function is unbounded (for example from considering $f(x^2-c), c> \max{x_i}$ and $n>c$) Now taking $f(a)$ to be large enough for some $a$ if $f(a)-y_i$ is not congruent to $2 \mod 4$ it can be written as a difference of 2 squares, one of which will be larger than $y_i$ because of the size of $f(a)$, which is a contradiction to $P(f(a); x^2-y)$. Now we know that if $x$ is sufficiently large either $x$ is of the form $m^2-x_i$ either $f(x)$ is congruent to a fixed value modulo 4, but this also takes place for all large enough $x$. Now take $y \equiv 1-y_i \mod 4$, and see that $f(y)+x$ is never a square for $x$ large enough not of the form $m^2-x_i$. And now if $f(y) \neq x_i$ taking $x=a^2-f(y)$ we achieve a contradiction, and otherwise we get that all the numbers congruent to $1-y_i \mod 4$ are of the form $x^2-x_i$ which is absurd, thus we have contradicted the initial assumption, so the function is injective.

Wrong, ignore.

Lemma 1 $f$ is unbounded, and it can attain big values with at least two different remainders modulo $4$. Suppose the contrary, then $f(x) \leq c$ for some $c$, or $f(x) \equiv t (mod 4)$. Take $y$ a little bit bigger than $c^2$ such that $y+t \equiv 3$ mod $4$, $x$ is such that $x+f(y)$ is a perfect square. Then $f(x)+y$ is a perfect square. $f(x) \leq c$ doesn't work because then $f(x)+y < (c+1)^2$ and $f(x) \equiv t$ doesn't work because squares do not give remainder $3$ modulo 4. This finishes the proof. Suppose $f$ is not injective, then $f(a)=f(b)=D$. $y=t^2-f(a)$, where $t^2>f(a)$, then $f(t^2-f(a))+a$ and $f(t^2-f(a))+b$. Because the difference of consecutive squares is not bounded, $f(t^2-f(a))$ is bounded. But then some value is attained infinitely many times. Call this value $c$ Take $f(q)=c$, $y=n^2-c$. So $f(n^2-c)+q$ is a perfect square. Firstly, it immediately follows that $f(n^2-c)$ is a constant. Secondly, because for $f(n^2-c)=f(a)$ perfect squares are achieved, this constant is equal to $f(a)$. Concluding it, we showed that if $f(a)=f(b)$, then there exists $c$ such that $f(n^2-c)=D$ for all $n^2>c$. Similarly one can show that $f(n^2-D)=c$ for all $n^2>D$ Hence, $f(n^2-c)=D$ and $f(n^2-D)=c$. Now suppose $f$ attains value $u^2-n^2+D$ for $u>n, n^2>D$. Then setting $x=n^2-D$, $y=f^{-1}(u^2-n^2+D)$ we get that $f^{-1}(u^2-n^2+D)+c$ is a perfect square, call it $r^2$, then $f^{-1}(u^2-n^2+D)=r^2-c$, taking $f$ on both sides we get $u^2-n^2+D=D$, so $u=n$ - contradiction. Hence $f$ doesn't attain values of the form $u^2-n^2+D$. But now note that all numbers from some point, that are not $\equiv D+2 (mod 4)$, are of this form. But it contradicts Lemma 1, hence we are done.

Suppose $f(a)=f(b)$ for $a\neq b$. Then $f(n^2-f(a))+a$ and $f(n^2-f(a))+b$ are both squares for all $n$ with $n^2>f(a)$, so $f(n^2-f(a))$ is bounded. Thus there is a value $y$ such that $f(n^2-f(a))=y$ for infinitely many $y$. For $x$ such that $x+y$ is a square, $f(x)+n^2-f(a)$ is a square for infinitely many $n$, so $f(x)=f(a)$. Thus for any $n$ and any $x$ such that $x+y$ is a square, $f(x)+n^2-f(a)$ is a square, so $f(n^2-f(a))+x$ is a square, and $f(n^2-f(a))=y$ for all $n$. There exists no $z$ such that $f(z)=m^2-n^2+f(a)$ for $n^2>f(a)$ except $z$ such that $f(z)=f(a)$ because if such a $z$ did exist, $z+y$ would be a square, so $m^2-n^2+f(a)+n_1^2-f(a)$ would be a square for all $n_1$ with $n_1^2>f(a)$ which is impossible. All odd numbers $N$ are $\left(\frac{N+1}{2}\right)^2-\left(\frac{N-1}{2}\right)^2$ and all multiples of $4$ $N$ are $\left(\frac{N+4}{4}\right)^2-\left(\frac{N-4}{4}\right)^2$, so all sufficiently large numbers (say less than a constant $C$) which are $f(a),f(a)+1,f(a)+3\bmod 4$ are not in the image of $f$. Taking a number $k$ which is $f(a)\bmod 4$ such that $[k,k+C]$ has no squares, we see that $f(z)+k$ is never a square for any $z$. Thus $f(k)+z$ is never a square, which is impossible, as desired.