Найдите наибольшее значение выражения $m^2+n^2$ для всевозможных пар $(m;n)$ натуральных чисел, таких что $1 \le m \le 1981$, $1 \le n \le 1981$ и $|n^2-mn-m^2|=1$.
Международная математическая олимпиада школьников (XXII, 1981 год)
Заметим прежде всего, что если пара $(n;m)$ натуральных чисел такова, что $$
(n^2-mn-m^2)^2=1,\tag{*}
$$
то $n\ge m$, причём $n=m$ лишь в случае $n=m=1$. Кроме того, если пара $(n_0;m_0)$ удовлетворяет условию (*) и $n_0\gt m_0$, то пара $(m_0;n_0-m_0)$ также ему удовлетворяет (проверьте это!). Положив $m_0=n_1$, $n_0-m_0=m_1$, получим $n_1\ge m_1$; если при этом $n_1>m_1$, то и пара $(n_2;m_2)$, где $n_2=m_1$, $m_2=n_1-m_1$, также удовлетворяет условию (*). Продолжая этот процесс образования новых пар, удовлетворяющих условию (*) (см. рисунок), мы через конечное число шагов получим пару $(1;1)$. В самом деле, вторые элементы построенных пар меньше первых их элементов, а последовательность первых элементов построенных пар убывает: $n_i\gt m_i=n_{i+1}$. Образование же новой пары из пары $(n';m')$ невозможно лишь в случае $n'=m'$:
тогда $n'-m'$ — не натуральное число. Отсюда вытекает, что последней образованной парой будет пара $(1;1)$.
Интересующие нас точки $(n;m)$ лежат на одной из гипербол $x^2-xy-y^2=1$, $x^2-xy-y^2=-1$. Преобразование точки $(x;y)$ в точку $(y;x-y)$, можно представлять себе как композицию трёх преобразований: (1) растяжение от прямой $l_1$ параллельно $l_2$ в $\dfrac{1+\sqrt5}2$ раз; (2) сжатие к прямой $l_2$ параллельно $l_1$ тоже в $\dfrac{1+\sqrt5}2$ раз; (3) симметрия относительно прямой $l_1$ ($A\to A_1\to A_2\to B$). Очевидно, это преобразование переводит красную гиперболу в синюю и наоборот.
Теперь заметим, что если пара $(n';m')$ получена из пары $(n;m)$ указанным преобразованием, то $$
n=m'+n',\quad m=n'.\tag{**}
$$
Это означает, что вся последовательность пар, удовлетворяющих свойству (*), получается единственным образом из пары $(1;1)$ — с помощью преобразования (**). При этом последовательности и первых, и вторых элементов построенных таким образом пар возрастают. Вспомнив об ограничениях $1\le n\le1981$, $1\le m\le1981$, получим, что наибольшее значение выражения $n^2+m^2$ будет для такой пары $(n;m)$ натуральных чисел, у которой $n\le1981$, а $m+n\gt1981$. Последовательно выписывая пары, получающиеся из $(1;1)$ преобразованием (**):
$$
(1;1),~~(2;1),~~(3;2),~~(5;3),~~(8;5),~~(13;8),~~\ldots,
$$
находим интересующую нас пару $(1597;987)$, так что ответ в нашей задаче — число $1597^2+987^2$.
Попутно мы получили следующий замечательный факт: все пары натуральных чисел $(n;m)$, для которых $|n^2-mn-m^2|=1$ и $n\gt m$, имеют вид $(f_{i+1};f_i)$, где $f_i$ и $f_{i+1}$ — соседние члены последовательности Фибоначчи. Попробуйте сформулировать его на «геометрическом» языке целых точек гипербол, изображённых на нашем рисунке.
