Русская Википедия:Прыжки Виета

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

История

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

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

«

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

»
— Анонимус

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

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

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

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

ММО 1988, задача № 6. Пусть a и b — положительные целые числа такие, что Шаблон:Math делит Шаблон:Math. Докажите, что Шаблон:Math — это полный квадрат.[6][7]

  1. Пусть Шаблон:Math. Предположим, что существует какое-то решение, для которого Шаблон:Math не является полным квадратом.
  2. Для такого значения Шаблон:Math, рассмотрим решение Шаблон:Math, минимизирующее значение Шаблон:Math. Без потери общности можно считать, что Шаблон:Math. Переписывая выражение для Шаблон:Math и заменяя Шаблон:Math на Шаблон:Math, получаем квадратное уравнение Шаблон:Math. По построению Шаблон:Math является корнем этого уравнения. По формулам Виета второй корень может быть представлен в виде Шаблон:Math.
  3. Из первого выражения для Шаблон:Math следует, что Шаблон:Math является целым числом, а из второго — что Шаблон:Math. Так как Шаблон:Math, то Шаблон:Math является положительным. Наконец, из Шаблон:Math следует, что Шаблон:Math и поэтому Шаблон:Math, что противоречит минимальности решения Шаблон:Math.

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

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

  1. Отдельно рассматривается случай равенства Шаблон:Math. В дальнейшем предполагается, что Шаблон:Math.
  2. Фиксируются значения Шаблон:Math и Шаблон:Math. Соотношение между Шаблон:Math и Шаблон:Math приводится к форме квадратного уравнения с коэффициентами зависящими от Шаблон:Math и Шаблон:Math, одним из корней которого является Шаблон:Math. Другой корень Шаблон:Math определяется с помощью формул Виета. 
  3. Показывается, что для всех Шаблон:Math больших некоторых базовых значений, выполняется неравенство Шаблон:Math, причём Шаблон:Math является целым числом. Таким образом, от решения Шаблон:Math можно спуститься к решению Шаблон:Math и повторять этот процесс, пока не получится решение с базовыми значениями.
  4. Утверждение доказывается для базовых значений. Так как Шаблон:Math остаётся неизменным в процессе спуска, отсюда следует справедливость доказываемого утверждения для всех упорядоченных пар Шаблон:Math.
Пример

Пусть положительные целые числа Шаблон:Math и Шаблон:Math таковы, что Шаблон:Math делит Шаблон:Math. Требуется доказать, что Шаблон:Math.[9]

  1. Если Шаблон:Math, то Шаблон:Math должно делить Шаблон:Math. Откуда Шаблон:Math и поэтому Шаблон:Math. В дальнейшем без потери общности считаем, что Шаблон:Math.
  2. Пусть Шаблон:Math. Преобразованием этого равенства и заменой Шаблон:Math на Шаблон:Math, получаем квадратное уравнение Шаблон:Math, одним из корней которого является Шаблон:Math. По формулам Виета второй корень может быть представлен в виде: Шаблон:Math.
  3. Первое представление показывает, что Шаблон:Math является целым числом, а второе представление, что это число положительно. Неравенство Шаблон:Math влечёт, что Шаблон:Math, если Шаблон:Math.
  4. Таким образом, базовым случаем является значение Шаблон:Math. При этом значение Шаблон:Math должно делить Шаблон:Math, и поэтому Шаблон:Math равно 1 или 2. Случай Шаблон:Math невозможен, поскольку Шаблон:Math. В случае Шаблон:Math имеем Шаблон:Math. Так как значение Шаблон:Math не менялось в процессе спуска, получаем, что Шаблон:Math, то есть Шаблон:Math, для всех упорядоченных пар Шаблон:Math.

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

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

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

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

  1. Пусть Шаблон:Math. Зафиксируем значение Шаблон:Math и рассмотрим гиперболу Шаблон:Math, задаваемую уравнением Шаблон:Math. Тогда Шаблон:Math является точкой на этой гиперболе.
  2. Если Шаблон:Math, то Шаблон:Math, что тривиально удовлетворяет утверждению задачи.
  3. Пусть Шаблон:Math — это целая точка на «верхней» ветви гиперболы Шаблон:Math с Шаблон:Math. Тогда из формул Виета следует, что Шаблон:Math — это целая точка на «нижней» ветви гиперболы Шаблон:Math. Отражением этой точки является точка Шаблон:Math на исходной «верхней» ветви. У полученной точки вторая координата меньше чем у исходной, а значит она находится ниже исходной точки.
  4. Этот процесс может быть повторен. Из уравнения гиперболы Шаблон:Math следует, что при этом получаемые точки остаются в пределах первого квадранта. Таким образом, повторение процесса закончится при получении значения Шаблон:Math. Его подстановка в уравнение гиперболы Шаблон:Math даёт Шаблон:Math, что и требовалось доказать.

См. также

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Rq Шаблон:Избыток цитат

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite journal
  2. ↑ 2,0 2,1 Шаблон:Книга
  3. ↑ Шаблон:Cite web
  4. ↑ Возвращение легенды о вопросе номер 6, Numberphile #93, YouTube. Шаблон:Wayback
  5. ↑ Шаблон:Статья
  6. ↑ Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Прыжки_Виета&oldid=10657402