Kvant Math Problem 718
The equation is
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m19s
Source on kvant.digital
Problem
Find the maximum value of the expression $m^2+n^2$ for all pairs of natural numbers $(m;n)$ such that $1 \le m \le 1981$, $1 \le n \le 1981$, and $|n^2-mn-m^2|=1$.
International Mathematical Olympiad for School Students (XXII, 1981)
Exploration
The equation is
$$|n^2-mn-m^2|=1.$$
The quadratic form $n^2-mn-m^2$ is closely related to the Fibonacci numbers, because
$$F_{k+1}^2-F_{k+1}F_k-F_k^2=(-1)^k.$$
Checking small cases:
$$(1,1):\quad 1-1-1=-1,$$
$$(1,2):\quad 4-2-1=1,$$
$$(2,3):\quad 9-6-4=-1,$$
$$(3,5):\quad 25-15-9=1.$$
These are consecutive Fibonacci numbers.
The problem asks for the largest possible value of $m^2+n^2$ under the constraints $m,n\le 1981$. If every solution consists of consecutive Fibonacci numbers, then we only need the largest consecutive Fibonacci pair not exceeding $1981$.
The Fibonacci numbers near $1981$ are
$$987,\ 1597,\ 2584.$$
Since $2584>1981$, the largest admissible pair should be $(987,1597)$, giving
$$987^2+1597^2.$$
Compute:
$$987^2=974169,$$
$$1597^2=2550409,$$
hence
$$987^2+1597^2=3524578.$$
The crucial point is proving that every positive integer solution of
$$|n^2-mn-m^2|=1$$
is a pair of consecutive Fibonacci numbers. A descent argument analogous to the Euclidean algorithm should accomplish this. If $n\ge m$, then from
$$n^2-mn-m^2=\pm1$$
we obtain
$$(n-m)^2-m(n-m)-m^2=\mp1.$$
Thus $(m,n-m)$ is another solution. Repeating reduces the larger coordinate and eventually reaches $(1,1)$. Reversing the process reconstructs the Fibonacci recurrence.
Problem Understanding
We must determine the maximum value of
$$m^2+n^2$$
among all natural-number pairs $(m,n)$ satisfying
$$1\le m,n\le 1981, \qquad |n^2-mn-m^2|=1.$$
This is a Type C problem.
The core difficulty is the classification of all positive integer solutions of the Pell-type equation
$$|n^2-mn-m^2|=1.$$
The answer is
$$3524578.$$
Intuitively, the solutions appear to be consecutive Fibonacci numbers, and the largest admissible such pair is $(987,1597)$.
Proof Architecture
First lemma: if $(m,n)$ satisfies $|n^2-mn-m^2|=1$, then $m\ne n$ unless $(m,n)=(1,1)$; this follows directly from substituting $m=n$.
Second lemma: if $n>m$ and $(m,n)$ satisfies $|n^2-mn-m^2|=1$, then $(m,n-m)$ also satisfies the same condition; this is obtained by direct expansion.
Third lemma: repeated application of the previous lemma reduces every positive solution to $(1,1)$; the larger coordinate strictly decreases at each step.
Fourth lemma: reversing the reduction transforms $(a,b)$ with $a\ge b$ into $(a,a+b)$, so every solution is generated from $(1,1)$ by repeated applications of $(x,y)\mapsto(x,x+y)$ after ordering the coordinates.
Fifth lemma: the resulting sequence of ordered pairs is exactly
$$(F_k,F_{k+1}),$$
the consecutive Fibonacci numbers.
The hardest direction is proving that no other solutions exist. The descent lemma is the step most likely to fail under scrutiny.
Solution
Let
$$Q(m,n)=n^2-mn-m^2.$$
We seek the maximum of $m^2+n^2$ subject to
$$|Q(m,n)|=1, \qquad 1\le m,n\le 1981.$$
Assume first that $n\ge m$.
If $n=m$, then
$$Q(m,m)=m^2-m^2-m^2=-m^2.$$
The condition $|Q(m,m)|=1$ yields $m=1$. Hence the only solution with $m=n$ is $(1,1)$.
Now suppose $n>m$. Put
$$r=n-m.$$
Then $r>0$, and
$$\begin{aligned} Q(m,r) &=r^2-mr-m^2\ &=(n-m)^2-m(n-m)-m^2\ &=n^2-3mn+m^2-mn+m^2-m^2\ &=n^2-4mn+m^2. \end{aligned}$$
Using
$$Q(m,n)=n^2-mn-m^2,$$
we obtain
$$\begin{aligned} Q(m,r) &=-(n^2-mn-m^2)\ &=-Q(m,n). \end{aligned}$$
Thus
$$Q(m,n)=\pm1 \quad\Longrightarrow\quad Q(m,n-m)=\mp1.$$
Hence $(m,n-m)$ is again a positive integer solution of
$$|Q|=1.$$
The larger coordinate of $(m,n-m)$ is strictly smaller than $n$, so repeated application of this transformation eventually reaches a solution with equal coordinates. As shown above, the only such solution is $(1,1)$.
Therefore every positive solution can be reduced to $(1,1)$ by repeatedly replacing the larger coordinate by the difference of the two coordinates.
Now reverse the process. If $(a,b)$ is a solution with $a\ge b$, then the preceding reduction arose from
$$(a,b)\longleftarrow(a,a+b).$$
Starting from $(1,1)$ and repeatedly applying this inverse step, while keeping the pair ordered, we obtain
(1,1), \ (1,2), \ (2,3), \ (3,5), \ (5,8), \ldots ] These are precisely the pairs
(F_k,F_{k+1}),
where $(F_k)$ is the Fibonacci sequence defined by
F_1=F_2=1,\qquad F_{k+2}=F_{k+1}+F_k.
Since every solution reduces to $(1,1)$ and every reverse step produces the next consecutive Fibonacci pair, the positive integer solutions of
|n^2-mn-m^2|=1
$$are exactly the pairs$$
(F_k,F_{k+1})
and their reversals. The Fibonacci numbers near $1981$ are
987=F_{16},\qquad 1597=F_{17},\qquad 2584=F_{18}.
Since $2584>1981$, the largest admissible solution is
(m,n)=(987,1597)
$$or its reversal. To verify optimality, compare the two largest admissible consecutive Fibonacci pairs:$$
(610,987):
\quad
610^2+987^2=1349569,
$$and$$
(987,1597):
\quad
987^2+1597^2=3524578.
The latter is larger. No admissible solution can contain a coordinate exceeding $1597$, because the next Fibonacci number is $2584>1981$. Therefore the maximum value is [ \begin{aligned} 987^2+1597^2 &=974169+2550409\ &=3524578. \end{aligned} ] Hence
\boxed{3524578},
with equality for $(m,n)=(987,1597)$ and $(1597,987)$. ## Verification of Key Steps The first delicate step is the identity
Q(m,n-m)=-Q(m,n).
A direct computation gives [ \begin{aligned} Q(m,n-m) &=(n-m)^2-m(n-m)-m^2\ &=n^2-3mn+m^2-mn+m^2-m^2\ &=-(n^2-mn-m^2), \end{aligned} ] which confirms the sign reversal exactly. The second delicate step is termination of the descent. When $n>m$, the replacement
(m,n)\mapsto(m,n-m)
produces another positive solution and decreases the larger coordinate from $n$ to at most $n-1$. Since the larger coordinate is a positive integer, infinite descent is impossible. The process must end at a solution with equal coordinates. The third delicate step is uniqueness of the endpoint. If a terminal solution had equal coordinates $(t,t)$, then
|Q(t,t)|=|-t^2|=t^2.
Thus $t^2=1$, giving $t=1$. Every descent chain ends at the unique pair $(1,1)$, which is why the reverse construction yields all solutions. ## Alternative Approaches A more algebraic proof uses the identity
F_{k+1}^2-F_{k+1}F_k-F_k^2=(-1)^k,
$$which follows by induction. One then proves that every solution of$$
|n^2-mn-m^2|=1
arises from the action of the unit group of the quadratic ring $\mathbb Z!\left[\frac{1+\sqrt5}{2}\right]$. The positive solutions are exactly consecutive Fibonacci numbers. The descent method is preferable here because it uses only elementary arithmetic. The transformation $(m,n)\mapsto(m,n-m)$ mirrors the Euclidean algorithm, classifies all solutions directly, and leads immediately to the largest admissible Fibonacci pair below the bound $1981$.