Прыжки Виета

Прыжки Виета — это относительно новый метод решения олимпиадных математических задач. Первая такая задача была предложена на 29-й международной математической олимпиаде в 1988 году, причём эта задача считалась наиболее сложной из предложенных на олимпиаде:[1]

Среди одиннадцати школьников, получивших максимальный балл за решение этой задачи, был будущий Филдсовский лауреат Нго Бао Тяу (16 лет)[2]. Два других будущих Филдсовских лауреата, Теренс Тао (12 лет) и Элон Линденштраусс (17 лет), на шестой задаче заработали всего по одному баллу[3].

Стандартные прыжки Виета проводят доказательство от противного в три шага:[4]

1. Предполагается, что существуют числа, связанные данным соотношением, но не удовлетворяющие доказываемому утверждению.
2. Рассматривается минимальное решение (A, B) относительно некоторой функции (например, A + B). Затем исходное соотношение преобразуется в квадратное уравнение с коэффициентами, зависящими от B, и один из корней которого равен A. Используя формулы Виета, находится второй корень этого уравнения.
3. Показывается, что второй корень даёт решение, которое имеет меньшее значение выбранной функции. Таким образом, получается противоречие с минимальностью значения функции на исходном решении, а поэтому предположение из шага 1 является ложным.

Пример

ММО 1988, задача № 6. Пусть a и b — положительные целые числа такие, что ab + 1 делит a² + b². Докажите, что a² + b²ab + 1 — это полный квадрат.[5][6]

1. Пусть k = a² + b²ab + 1. Предположим, что существует какое-то решение, для которого k не является полным квадратом.
2. Для такого значения k, рассмотрим решение (A,B), минимизирующее значение A + B. Без потери общности можно считать, что A ≥ B. Переписывая выражение для k и заменяя A на x, получаем квадратное уравнение x² – (kB)x + (B² – k) = 0. По построению x₁ = A является корнем этого уравнения. По формулам Виета второй корень может быть представлен в виде x₂ = kB – A = B² – kA.
3. Из первого выражения для x₂ следует, что x₂ является целым числом, а из второго — что x₂ ≠ 0. Так как k = x₂² + B²x₂B + 1 > 0, то x₂ является положительным. Наконец, из A ≥ B следует, что x₂ = B² − kA < A и поэтому x₂ + B < A + B, что противоречит минимальности решения (A,B).

Метод непрерывного спуска прыжками Виета используется для доказательства некоторого утверждения о постоянной k, зависящей от соотношения между целыми числами a и b. В отличие от стандартных прыжков Виета, непрерывный спуск не является доказательством от противного и состоит из следующих четырёх шагов[7]:

1. Отдельно рассматривается случай равенства a = b. В дальнейшем предполагается, что a > b.
2. Фиксируются значения b и k. Соотношение между a, b и k приводится к форме квадратного уравнения с коэффициентами зависящими от b и k, одним из корней которого является x₁ = a. Другой корень x₂ определяется с помощью формул Виета. 
3. Показывается, что для всех (a, b) больших некоторых базовых значений, выполняется неравенство 0 < x₂ < b < a, причём x₂ является целым числом. Таким образом, от решения (a, b) можно спуститься к решению (b, x₂) и повторять этот процесс, пока не получится решение с базовыми значениями.
4. Утверждение доказывается для базовых значений. Так как k остаётся неизменным в процессе спуска, отсюда следует справедливость доказываемого утверждения для всех упорядоченных пар (a, b).

Пример

Пусть положительные целые числа a и b таковы, что ab делит a² + b² + 1. Требуется доказать, что 3ab = a² + b² + 1.[8]

1. Если a = b, то a² должно делить 2a² + 1. Откуда a = b = 1 и поэтому 3(1)(1) = 1² + 1² + 1. В дальнейшем без потери общности считаем, что a > b.
2. Пусть k = a² + b² + 1ab. Преобразованием этого равенства и заменой a на x, получаем квадратное уравнение x² − (kb)x + (b² + 1) = 0, одним из корней которого является x₁ = a. По формулам Виета второй корень может быть представлен в виде: x₂ = kb − a = b² + 1a.
3. Первое представление показывает, что x₂ является целым числом, а второе представление, что это число положительно. Неравенство a > b влечёт, что x₂ = b² + 1a < b, если b > 1.
4. Таким образом, базовым случаем является значение b = 1. При этом значение a должно делить a² + 2, и поэтому a равно 1 или 2. Случай a = 1 невозможен, поскольку a ≠ b. В случае a = 2 имеем k = a² + b² + 1ab = 62 = 3. Так как значение k не менялось в процессе спуска, получаем, что a² + b² + 1ab = 3, то есть 3ab = a² + b² + 1, для всех упорядоченных пар (a, b).

Прыжки Виета могут быть описаны в терминах целых точек на гиперболах в первом квадранте.[1] При этом процесс нахождения меньшего корня соответствует поиску меньших целых точек на гиперболе в пределах первого квадранта. Этот процесс может быть описан следующим образом:

1. Из данного условия получается уравнение семейства гипербол, которые не изменяются при перестановке x и y местами. Другими словами, эти гиперболы симметричны относительно прямой y = x.
2. Требуемое утверждение доказывается для точек пересечения гипербол и прямой y = x.
3. Предполагается, что (x, y) — целая точка на некоторой гиперболе, причём без потери общности x < y. Тогда по формулам Виета, находится целая точка тем же значением первой координаты на другой ветви гиперболы. Тогда отражением этой точки относительно прямой y = x получается новая целая точка на исходной ветви гиперболы.
4. Показывается, что этот процесс приводит к нахождению меньших точек на той же ветви параболы, пока выполняется определённое условие (например, x = 0). Подставляя это условие в уравнение гиперболы, проверяется, что для него выполняется доказываемое утверждение.

Пример

Применим описанный метод к задаче № 6 с ММО 1988: Пусть a и b — положительные целые числа такие, что ab + 1 делит a² + b². Докажите, что a² + b²ab + 1 — это полный квадрат.

1. Пусть a² + b²ab + 1 = q. Зафиксируем значение q и рассмотрим гиперболу H, задаваемую уравнением x² + y² − qxy − q = 0. Тогда (a,b) является точкой на этой гиперболе.
2. Если x = y, то x = y = q = 1, что тривиально удовлетворяет утверждению задачи.
3. Пусть (x, y) — это целая точка на «верхней» ветви гиперболы H с x < y. Тогда из формул Виета следует, что (x, qx − y) — это целая точка на «нижней» ветви гиперболы H. Отражением этой точки является точка (qx − y, x) на исходной «верхней» ветви. У полученной точки вторая координата меньше чем у исходной, а значит она находится ниже исходной точки.
4. Этот процесс может быть повторен. Из уравнения гиперболы H следует, что при этом получаемые точки остаются в пределах первого квадранта. Таким образом, повторение процесса закончится при получении значения x = 0. Его подстановка в уравнение гиперболы H даёт q = y², что и требовалось доказать.

• Формулы Виета
• Доказательство от противного
• Метод бесконечного спуска
• Число Маркова
• Сетка Аполлония

• К. Кноп, Прыжки Виета, Элементы.ру