WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

История

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

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

Среди одиннадцати школьников, получающих максимальный балл за решение этой задачи, был будущий Филдсовский лауреат Нго Бао Тяу.[2]

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

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

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

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

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

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

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

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

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

  1. Если a = b, то a2 должно делить 2a2 + 1. Откуда a = b = 1 и поэтому 3(1)(1) = 12 + 12 + 1. В дальнейшем без потери общности считаем, что a > b.
  2. Пусть k = a2 + b2 + 1ab. Преобразованием этого равенства и заменой a на x, получаем квадратное уравнение x2 − (kb)x + (b2 + 1) = 0, одним из корней которого является x1 = a. По формулам Виета второй корень может быть представлен в виде: x2 = kb − a = b2 + 1a.
  3. Первое представление показывает, что x2 является целым числом, а второе представление, что это число положительно. Неравенство a > b влечёт, что x2 = b2 + 1a < b, если b > 1.
  4. Таким образом, базовым случаем является значение b = 1. При этом значение a должно делить a2 + 2, и поэтому a равно 1 или 2. Случай a = 1 невозможен, поскольку a ≠ b. В случае a = 2 имеем k = a2 + b2 + 1ab = 62 = 3. Так как значение k не менялось в процессе спуска, получаем, что a2 + b2 + 1ab = 3, т.е. 3ab= a2 + b2 + 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 делит a2 + b2. Докажите, что a2 + b2ab + 1 — это полный квадрат.

  1. Пусть a2 + b2ab + 1 = q. Зафиксируем значение q и рассмотрим гиперболу H, задаваемую уравнением x2 + y2 − 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 = y2, что и требовалось доказать.

См. также

Примечания

  1. 1 2 Arthur Engel. Problem Solving Strategies. — Springer, 1998. — P. 127. — ISBN 978-0-387-98219-9.
  2. ↑ Results of International Mathematical Olympiad 1988. Imo-official.org. Проверено 3 марта 2013.
  3. ↑ Yimin Ge (2007). “The Method of Vieta Jumping” (PDF). Mathematical Reflections. 5.
  4. ↑ AoPS Forum – One of my favourites problems, yeah!. Artofproblemsolving.com. Проверено 3 марта 2013.
  5. ↑ K. S. Brown. N = (x^2 + y^2)/(1+xy) is a Square. MathPages.com. Проверено 26 сентября 2016.
  6. ↑ AoPS Forum — Lemur Numbers. Artofproblemsolving.com. Проверено 3 марта 2013.
  7. ↑ AoPS Forum – x*y | x^2+y^2+1. ArtOfProblemSolving.com (7 июня 2005). Проверено 3 марта 2013.

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии