Experimenting with small values suggests that the solutions of $n^2 - mn - m^2 = 1$ or $-1$ are successive Fibonacci numbers. So suppose $n > m$ is a solution. This suggests trying $m+n$, $n$: $(m+n)^2 - (m+n)n - n^2 = m^2 + mn - n^2 = -(n^2 - mn - m^2) = 1$ or $-1$. So if $n > m$ is a solution, then $m+n$, $n$ is another solution. Running this forward from $2$,$1$ gives $3$,$24;$5$,$3$;$8$,$5$;$13$,8$;$21$,$13$;$34$,$21$;$55$,$34$;$89$,$55$;$144$,$89$;$233$,$144$;$377$,$233$;$610$,$377$;$987$,$610$;$1597$,$987$;$2584$,$1597$. But how do we know that there are no other solutions? The trick is to run the recurrence the other way. For suppose $n > m$ is a solution, then try $m$, $n-m$: $m^2 - m(n-m) - (n-m)^2 = m^2 + mn - n^2$ $= -(n^2 - mn - m^2) = 1$ or $-1$, so that also satisfies the equation. Also if $m > 1$, then $m > n-m$ (for if not, then $n \ge 2m$, so $n(n - m) \geq 2m^2$, so $n^2 - nm - m^2 \ge m^2 > 1$). So given a solution $n > m$ with $m > 1$, we have a smaller solution $m > n-m$. This process must eventually terminate, so it must finish at a solution $n$, $1$ with $n > 1$. But the only such solution is $2$, $1$. Hence the starting solution must have been in the forward sequence from $2$, $1$. Hence the solution to the problem stated is $1597^2 + 987^2$

The result in this IMO problem is due to J. Wasteels, from the year 1902: J. Wasteels, Quelques Proprietes des Nombres de Fibonacci, Mathesis 3 (1902), pp 60-62 Dominique Cassini proved in 1680 that two consecutive Fibonacci numbers $x$ and $y$ always satisfy the equation \[ x^2-xy-y^2~=~\pm1. \]The converse statement (that all solutions to this equation are consecutive Fibonacci numbers) is less obvious, and has been established much later by Wasteels in 1902. This is also exercise 6.44 in the book "Concrete Mathematics" by Ronald Graham, Donald Knuth, and Oren Patashnik. The proof technique used by Wasteels is the technique that children in mathematical olympiad circles call "Vieta jumping".

Clearly, we have $n^2-mn-m^2= \pm 1$ so by the quadratic formula we have $n=\dfrac{m \pm \sqrt{5m^2 \pm 4}}{2}$ It is well known (well, maybe not WELL known) that $5x^2 \pm 4$ is a square number iff $x$ is a Fibonacci number. So, $m$ must be a Fibonacci number. Clearly if $m= 1597$, $n$ will be too large and if $m>1587$ then $m$ is too large. So, considering $m=987$ we get $n=1597$ giving the answer to be $987^3+1597^3=5034507976$. Remark: The original problem statement asks for $m^3+n^3$, not $m^2+n^2$.

blackbluecar wrote: Remark: The original problem statement asks for $m^3+n^3$, not $m^2+n^2$. I'm pretty sure this is not the case. Where did you get it from?

ZETA_in_olympiad wrote: blackbluecar wrote: Remark: The original problem statement asks for $m^3+n^3$, not $m^2+n^2$. I'm pretty sure this is not the case. Where did you get it from? Download the official problem statements from the imo website. It says $m^3+n^3$ there.

a very wrong solution used to be here

The $k^2-5m^2 = \pm 4$ Pell-like equation has quasi-Fibonacci like solutions, which motivates the following claim: Claim. If $(m, n)$ is a solution, then so is $(n, m+n)$. Proof. Algebra. $\blacksquare$ This means that all solutions can be generated from the minimal solution $(1, 1)$; in particular, the pair $(1597, 987)$ maximizes the desired value.

Let $\phi$ be the golden ratio. We work in the ring $\mathbb Z\left[ \frac{1 + \sqrt{5}}{2} \right]$. Indeed note that this is a ring as it trivially closed under addition, and it is closed under multiplication since $\phi^2 = \phi+ 1$. By defining the norm \[ \| a + b\phi\| = (a + b\phi)\left(a - \frac{b}{\phi} \right) = a^2 + ab - b^2 \text{\tiny (hey, where've I seen this before?)\normalsize}, \]one can note that the units of this ring generate all the solutions to a slightly different equation. Even more, the ring has a fundamental unit, namely $\phi$. For the sake of proving this I'll prove it cause its kinda neat. $\textbf{Claim.}$ Let $a$, $b$ be integers such that $\frac{1}{a + b\phi} \in \mathbb Z \left[ \phi \right]$. Then $a + b\phi = \pm \phi^N$, for some integer $N$. $\emph{Proof.}$ Suppose not. By negating the value we can consider the set of units with real value more than $1$. Clearly $\phi$ is in this set. It is sufficient to show that there does not exist an element with real value between $1$ and $\phi$ in this set, as otherwise we can just keep multiplying by $\frac{1}{\phi}$ till we get there. Suppose $p + q\phi$ was such an element. We have \[ 1 < p + q\phi < \phi. \]On the other hand, $p - \frac{q}{\phi} = p + q - q\phi \in (\phi - 1, 1)$ because $p + q\phi$ is a unit. Multiplying by $\phi$, we have \[ 1 < p + q\phi < \phi, \]and \[ 1 < p\phi - q < \phi.\]Now if $p \ge 2$, then $q \ge \phi$, but on the other hand, $q \le 1 - \frac{2}{\phi}$. These are incompatible. If $p \le 0$, then $1 < -q$, but on the other than $\phi - 1 < q$. These too are incompatible. It remains to consider $p=1$. But then, we find that $0 < q < 1$, clearly absurd. As such there can be no unit between $1$ and $\phi$. $\square$ We now classify all solutions to the equation we have (but not yet the given one.) We have $(a,b) = (0,1)$ corresponding to the fundamental solution, and it's moreover easy to see that $\phi^n = F_{n - 1} + F_{n}\phi$, where $F_n$ is defined as the Fibonacci sequence for all integers $n$ with $F_1 = F_2 = 1$. Therefore, $(\pm F_{n-1}, \pm F_{n})$ are all the solutions to the original equation, up to a choice of one sign. But then note that going the other way, the Fibonacci sequence goes \[ 1, 1, 0, 1, -1, 2, -3, 5, -8, \dots\]and in particular, \[ F_{-n} = (-1)^{n + 1}F_{n}. \]then, by flipping signs repeatedly, we obtain a slightly different solution set; namely, \[ (n,m) = (\pm F_n, \pm F_{n - 1}). \]At last, we compute the answer to be $\boxed{1597^2 + 987^2}$. We are done.

Let $(n, m)$ be a solution of $(n^2 - mn - m^2)^2 = 1$. Then obviously we have $n > m$, except the case $(n, m) = (1, 1)$. Now consider the following claim: Claim: If $(n, m)$ is a solution, then $(n+m, n)$ is a solution. Proof. Note that $((n+m)^2 - n(n+m) - n^2)^2 = (m^2 + mn - n^2)^2 = (n^2 - mn - m^2)^2 = 1$, so $(n+m, m)$ is a solution. $\square$ Now if $(n, m)$ is a solution, then draw arrow $(n, m)$ to $(n+m, n)$. Then it's not hard to see that the above graph contains all solution of $(n^2 - mn - m^2)^2 = 1$ and if $m=n$, then obviously we have $(m, n) = (1, 1)$. So if $(n, m)$ is a solution, then $(n, m) = (F_k, F_{k-1})$ for some $k \ge 1$. Hence the maximum value of $m^2 + n^2 = 1597^2 + 987^2 = 3524578$. $\blacksquare$

Vieta Jumping tells us a working pair $(m,n)$ implies \[(m,m-n), (-m-n,n), (n,-m), (-n,m)\] are also working pairs. Euclid tells us all pairs lead down to either $m = \pm 1$ or $n = \pm 1$, from which we can find that the only working pairs have absolute values which are consecutive Fibonacci numbers. Thus our answer is $\boxed{987^2+1597^2}$. $\blacksquare$

Take a triple $(m,n)$ with $$m^{2}-mn-n^{2} = \pm 1.$$Take $m_{0} = \frac{-n^{2} \mp 1}{m} = n-m.$ Notice that, by Vieta's, $n_{0}$ satisfies $$m_{0}^{2}-m_{0}n - n^{2} = \pm 1, $$and $m_{0}$ is an integer. However, $m_{0}$ is non-positive. Thus, we take $-m_{0} = m_{1},$ which satisfies $$n^{2}-nm_{1}-m_{1}^{2} = \mp 1.$$Thus, we see that $(n, m_{1}) = (n, m-n)$ is another solution to our equation. Now, take a "fully reduced" pair $(m, n),$ i.e. a pair satisfying the equation, where if we try to generate a new pair in this way, one of the numbers will not be positive. Notice that such a pair satisfies $m = n,$ since otherwise $n > 0$ and $m_{1} = m-n > 0 $ are positive integers. Now, plugging in $m=n$ into our equation, we get that $m=n=1.$ We will now show that $(m, n) = (F_{k}, F_{k-1})$ for some $k$ via induction on the number of reductions we need to do to get to $(1,1)$ Obviously, if we do $0$ reductions, we just get $(1, 1).$ Now, for the inductive step, assume that, after $r$ reductions, the only possible pair is $(F_{k}, F_{k-1}).$ We need to show that after $r+1$ reductions, the only pair possible is $(F_{k+1}, F_{k}).$ Firstly, notice that doing one reduction to this will give us $(F_{k}, F_{k-1}). $ Next, assume for the sake of contradiction that some other pair $(m, n)$ becomes $(1,1).$ Then, we see that either $m-n \neq F_{n+1}-F_{n} = F_{n-1} $ or $n \neq F_{n} $ (or both), since otherwise the pair $(m, n)$ is the same as $(F_{k+1}, F_{k}).$ But, by the inductive hypothesis, we see that this is impossible, so we have a contradiction. So, now, we see that the largest pair we can have is $(F_{17}, F_{16}),$ or $(1597, 987),$ giving an answer of $987^{2} + 1597^{2} = 3524578.$

Let (n,m) be a solution. Obviously we have $n > m$, except (n, m) = (1, 1). Now by Vieta Jumping (m-n,m) works too. We can check that (n+m,n) works, since $((n+m)^2 - n(n+m) - n^2)^2 = (m^2 + mn - n^2)^2 = (n^2 - mn - m^2)^2 = 1$ $\Rightarrow$ (n+m,n) is a solution. Now since (n+m,n) is a solution, by Vieta jumping (-m, n) works too. We have the solutions jumping from (n,m) to (n+m,n), (m-n, m), (-m,n). By Vieta, these are the only solutions where m or n is one of the roots. We will finish this up by induction. The base case is showing that (1,1) works. Assume by induction that all numbers up to $(F_k, F_{k-1})$ have the form $(F_k, F_{k-1})$, then by this step $(n+m, n)$ or $(m-n, m)$ works, but they are both of the Fibonacci form $\Rightarrow$ all numbers are Fibonacci numbers $\Rightarrow$ we get that the max $m^2 + n^2 = F_{17}^2+F_{16}^2 = 1597^2 + 987^2 = 3524578$.

Vieta jump $(a,b) \mapsto (b-a,b)$, which is valid since we see $n>m$ unless $m=n=1$. Thus this process must terminate at $(1,1)$ and working backwards we see all solutions are pairs of Fibonacci numbers. The extraction is $987^2+1597^2=3524578$.

This feels more algmanip than heavyNT

We claim the solution is $max(m^2+n^2)=1597^2+987^2$. First, check that if $(n,m)$ is a solution to the given equation, then $(m,n-m)$ is also. As in $\{1\}$, the only solution is $(n,m)=(1,1)$, every solution can be descended into $(1,1)$, that is, $(m,n)=(F_k,F_{k-1})$ where $F_i$ is the $i$'th Fibonacci number. Furthermore, the last numbers on that sequence less or equal than $1981$ are $1597, 987$, hence $max(m^2+n^2)=1597^2+987^2$.