1981 IMO Problems/Problem 3

Revision as of 22:00, 28 October 2006 by Boy Soprano II (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Determine the maximum value of $\displaystyle m^2 + n^2$, where $\displaystyle m$ and $\displaystyle n$ are integers satisfying $m, n \in \{ 1,2, \ldots , 1981 \}$ and $\displaystyle ( n^2 - mn - m^2 )^2 = 1$.

Solution

We first observe that since $\displaystyle \gcd(m,n)|1$, $\displaystyle m$ and $\displaystyle n$ are relatively prime. In addition, we note that $\displaystyle n \ge m$, since if we had $\displaystyle n < m$, then $\displaystyle n^2 +nm -m^2 = n(n-m) - m^2$ would be the sum of two negative integers and therefore less than $\displaystyle -1$. We now observe

$\displaystyle (m+k)^2 -(m+k)m - m^2 = -(m^2 - km - k^2)$,

i.e., $\displaystyle (m,n) = (a,b)$ is a solution iff. $\displaystyle (b, a+b)$ is also a solution. Therefore, for a solution $\displaystyle (m, n)$, we can perform the Euclidean algorithm to reduce it eventually to a solution $\displaystyle (1,n)$. It is easy to verify that if $\displaystyle n$ is a positive integer, it must be either 2 or 1. Thus by trivial induction, all the positive integer solutions are of the form $\displaystyle (F_{n}, F_{n+1})$, where the $\displaystyle F_i$ are the Fibonacci numbers. Simple calculation reveals 987 and 1597 to be the greatest Fibonacci numbers less than 1981, giving $\displaystyle 987^2 + 1597^2$ as the maximal value Q.E.D.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources