Прыжки Виета

Одной из возможных пар чисел, удовлетворяющих условию, является (1, 1), а еще двумя — (1, 2) и (2, 1). Убедитесь, что для всех этих пар частное равно 3.

В качестве пары (a, b) можно брать любые два соседних числа в последовательности 1, 1, 2, 5, 13, 34, 89, 233, ... Попробуйте угадать, как образована эта последовательность, и доказать этот факт.

Постарайтесь доказать, что других решений, кроме пар чисел, перечисленных во второй подсказке, нет.

Сначала приведем «рафинированное» (в том же смысле, в котором рафинируют растительное масло, то есть очищенное от посторонних примесей) рассуждение, в котором никак не используются те сакральные сведения, которые мы упоминали в подсказках.

Пусть \(k=\frac{a^2+b^2+1}{ab}\). Если (а почему бы и нет?) a = b, то условие состоит в том, что 2a² + 1 делится на a². Поскольку 2a² всегда делится на a², то 1 также должно делиться на a², откуда a = 1. Но при a = b = 1 получаем \(k=\frac{1+1+1}{1}=3\), то есть для этого случая мы всё доказали.

Пусть теперь a ≠ b. Без ограничения общности можно считать a большим из двух чисел (то есть a > b). Попытаемся найти другую пару натуральных чисел (a', b'), которая также будет удовлетворять условию задачи, но будет меньше исходной.

Перепишем уравнение, связывающее a, b и k, в виде a² − kab + b² + 1 = 0. А чтобы было еще лучше понятно, что мы собираемся делать, вместо a напишем x. Это — квадратное уравнение (относительно x): \(x^2-kb\cdot x + (b^2+1)=0\). Мы не будем его решать, но вспомним, что его корни x₁ и x₂ (если они есть!) удовлетворяют теореме Виета:

Один из этих корней мы знаем: x₁ = a. Следовательно, мы можем сказать, что есть и второй корень \(x_2=kb-a=\frac{b^2+1}{a}\). Первое условие гарантирует, что x₂ является целым, а второе — что он является положительным. То есть x₂ — это натуральное число.

Таким образом, числа x₂ и b тоже удовлетворяют условию задачи, то есть \(x_2^2+b^2+1\) делится на x₂b, и частное от деления равно тому же числу k. При этом, поскольку мы предположили, что a > b, то \(x_2=\frac{b^2+1}{a}\le \frac{b^2+1}{b+1} < b\) при b > 1. Тогда в качестве меньшей пары мы можем взять пару (b, x₂).

Получается, что если b > 1, то теорема Виета дает нам возможность сделать «прыжок» от решения (a, b) к меньшему решению (a', b') = (b, kb − a).

А что будет, когда прыжки приведут нас к b = 1 (очевидно ведь, это рано или поздно должно случиться)?

При b = 1 уравнение будет иметь вид x² − kx + 2 = 0. Поскольку оно имеет натуральный корень a, а по теореме Виета произведение корней равно 2, то второй корень равен 2/a. А поскольку он же равен целому числу k − a, то a должно быть делителем числа 2. Это даёт две возможности:

1) если a = 2, то 4 − 2k + 2 = 0, откуда k = 3.
2) если a = 1, то 1 − k + 2 = 0, откуда снова k = 3.

Поскольку k оставалось одним и тем же при всех сделанных «прыжках», то k = 3 для любой пары чисел (a, b). На этом решение закончено.

А теперь попробуем разобраться, что именно мы делали и как пришли к нужному результату. Благодаря подсказкам было известно, что пара чисел (a, b), удовлетворяющая условию задачи, это какая-то из пар (1, 1), (1, 2), (2, 5), (5, 13), (13, 34), (34, 89) и т. д. Закономерность, которая прямо не бросалась в глаза, но наверняка была замечена при попытках решения, выглядит так: если между каждыми двумя числами пары вписать еще их разность, то получатся числа Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Для этой последовательности соотношение, связывающее три её последовательных члена, очень хорошо известно: f_n+2 = f_n + f_n+1. А так как «нашей» последовательностью являются числа Фибоначчи с четными номерами, то можно записать рекуррентное соотношение и для нее:

Действительно, 5 = 3·2 − 1, 13 = 3·5 − 2, 34=3·13 − 5 и так далее.

Здесь множитель 3 — тот самый, который мы обозначили в начале решения буквой k. Но мы-то не можем опираться на то, что нам нужно доказать, правда? И вот тут на помощь и приходит теорема Виета, благодаря которой переход от одного решения к соседнему делается совсем просто — «прыжком». При прыжке мы можем не знать, чему равно значение k, но гарантированно сдвинемся от большего решения к меньшему, сохранив то же самое значение k. А значит, рано или поздно дойдем до «наименьшего» решения. Дальнейшее уже — дело техники.

В статье английской Википедии Vieta jumping утверждается, что этот прием решения задач появился только в 1988 году в связи с задачей, предлагавшейся от Австралии на Международную олимпиаду школьников. Вот эта задача:

Пусть a и b — натуральные числа, для которых a² + b² делится на ab + 1. Докажите, что частное от этого деления — точный квадрат.

При этом пересказывается забавная история, впервые описанная в книге Артура Энгеля «Стратегии решения задач»:

«Никто из шести членов Австралийского задачного комитета не сумел решить ее. Двумя из этих членов были Дьердь Секереш и его жена, оба известные авторы и решатели задач. Поскольку эта задача относилась к теории чисел, ее послали четверым наиболее известным специалистам по теории чисел в Австралии. Их попросили подумать над задачей не более шести часов. В отведенное время никто из них не уложился. Поэтому задачный комитет предложил задачу в жюри XXIX Международной олимпиады, пометив ее двумя звёздочками, что означало очень высокую сложность, возможно, слишком высокую для олимпиады. После продолжительной дискуссии, жюри согласилось выбрать ее в качестве последней, самой трудной задачи олимпиады. 11 участников получили полные решения.»

На самом деле, безусловно, приём «прыжка» был известен задолго до этой олимпиады. В частности, задача, которую мы обсуждали, является частным случаем исследования хорошо известного диофантового уравнения Маркова, впервые исследованного замечательным русским математиком Андреем Андреевичем Марковым еще в XIX веке.

Уравнение Маркова имеет вид

Если положить в нём c = 1, получится ровно то уравнение, которым мы занимались. А существуют ли у уравнения Маркова решения, в которых c не равно 1? Безусловно, существуют. И у читателя уже есть всё необходимое для того, чтобы их найти.

Рис. 1. Пример семейства окружностей Аполлония. Рисунок с сайта en.wikipedia.org

Еще одной интереснейшей иллюстрацией идеи «прыжка Виета» могут служить множества Аполлония — семейства окружностей, в котором каждая касается трех других (рис. 1, см.: Apollonian gasket).

Если из такого семейства взять четверку окружностей, которые попарно касаются, то для их радиусов справедлива формула, впервые открытая знаменитым химиком (!) Фредериком Содди:

Если вместо радиусов r_i окружностей рассматривать их кривизны k_i (величины, обратные радиусам), то из формулы уходят сложные дроби:

Например, для четырех самых больших кругов на рисунке 1 кривизны равны −1, 2, 2 и 3 (знак «минус» пришлось поставить из-за того, что касание внутреннее). А отсюда, как может догадаться проницательный читатель, осталось всего полшага до утверждения о том, что кривизна каждого круга в (бесконечном) множестве Аполлония — целое число, и все эти числа могут быть получены друг из друга с помощью прыжков Виета.

Об уравнении Маркова можно прочитать в замечательной статье М. Г. Крейна «Диофантово уравнение А. А. Маркова», о фрактальных множествах Аполлония — в исследовании К. Миллер (на английском). Несколько красивых задач, в решении которых используется прием прыжка, можно найти здесь и здесь.