Прыжки Виета (Hjd'tn Fnymg)

Прыжки Виета (отражение корней) — метод доказательства, используемый в теории чисел; наиболее часто применяется для задач, в которых дано соотношение между двумя натуральными числами и требуется доказать некоторое связанное с ними утверждение. Существует несколько вариаций метода, которые так или иначе связаны с общей темой бесконечного спуска, где из данного решения находится новое (меньшее) решение с помощью формул Виета.

История

Прыжки Виета — это классический метод использующийся в теории квадратных диофантовых уравнений и бинарных квадратичных форм. Например, он использовался в 1879 году в анализе уравнения Маркова и в статье Миллса 1953 года.

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

Никто из шести членов австралийской задачной комиссии не смог решить эту задачу. Двое из них — Дьёрдь Секереш и его жена, оба известные решатели и составители задач. Так как это была задача по теории чисел, она была отправлена четырем самым известным австралийским математикам — специалистам в этой области. Им было предложено работать над ней в течение шести часов. Ни один из них не смог решить её за это время. Задачная комиссия представила ее в жюри 29-й ММО, отметив двумя звездочками. Это означало, что задача сверхсложная; возможно даже, слишком сложная для того, чтобы ее предлагать участникам олимпиады. После долгого обсуждения жюри всё-таки отважилось предложить её в качестве последней задачи на олимпиаде. Одиннадцать школьников представили её точные решения.Артур Энгель

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

Стандартные прыжки Виета

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

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

Пример

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

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² – k/A.
3. Из первого выражения для x₂ следует, что x₂ является целым числом, а из второго — что x₂ ≠ 0. Так как k = x₂² + B²/x₂B + 1 > 0, то x₂ является положительным. Наконец, из A ≥ B следует, что x₂ = B² − k/A < A и поэтому x₂ + B < A + B, что противоречит минимальности решения (A,B).

Непрерывный спуск прыжками Виета

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

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.

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

Геометрическая интерпретация

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

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², что и требовалось доказать.

См. также

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

Ссылки

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