Почему решение проблемы IMO 6 1988 года из одного абзаца работает?

Aug 17 2020

Эмануил Атанасов, который, как известно, решил «сложнейшую» задачу IMO в одном абзаце и получил специальный приз, привел приведенное ниже доказательство:

Вопрос: Пусть a и b - натуральные числа такие, что $ab+1$ разделяет $a^2+b^2$ Покажи то $\frac{a^2+b^2}{ab+1}$ это квадрат целого числа

Доказательство: $k=\frac{a^2+b^2}{ab+1} \implies a^2-kab+b^2=k, k\in \mathbb{Z}$ Предполагать $k$не идеальный квадрат. Отметим, что для любого интегрального решения$(a,b)$ у нас есть $a>0, b>0$так как k не является полным квадратом. Позволять$(a,b)$ - интегральное решение с $a>0, b>0$ и $a+b$минимум. Получим из него другое интегральное решение$(a',b)$ с участием $a'>0 , \ b>0$ и $a'+b<a+b$. Противоречие (Мы опускаем аргумент, чтобы прийти к$(a',b)$)

$a'=0$ достаточно для $k$квадрат, но в целом это не так. Это доказательство, кажется, подразумевает$a'=0$ для всех решений $(a,b)$. Единственное противоречие - это минимальность$a+b$а не предположение $k$не идеальный квадрат. Как тривиально утверждение следует из этого доказательства?

РЕДАКТИРОВАТЬ: вот доказательство изменено, но без предположения $k$ не идеальный квадрат.

$k=\frac{a^2+b^2}{ab+1} \implies a^2-kab+b^2=k, k\in \mathbb{Z}$ Позволять $(a,b)$ - интегральное решение с $a>0, b>0$ и $a+b$минимум. Получим из него другое интегральное решение$(a',b)$ с участием $a'>0 , \ b>0$ и $a'+b<a+b$. Противоречие (Мы опускаем аргумент, чтобы прийти к$(a',b)$)

Я также убрал второе предложение, потому что $a,b>0$дается в вопросе. Что это доказательство подразумевает, а первое - нет?

Ответы

4 JoséCarlosSantos Aug 17 2020 at 14:04
  1. Если есть решения $(a,b)$ для которого $k$ не идеальный квадрат, тогда $a,b>0$.
  2. Также, если есть решения $(a,b)$ для которого $k$ не является идеальным квадратом, то среди этих решений будет одно, для которого $a+b$ минимально.
  3. Затем автор находит другое решение $(a',b)$ с участием $a'<a$, откуда следует, что $a'+b<a+b$.
  4. Но это невозможно, поскольку мы предполагали, что $(a,b)$ было решением, для которого $a+b$ принимает наименьшее значение.
2 AlexeyBurdin Aug 17 2020 at 14:57

Полное решение дословно с en.wiki/Vieta jump :

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

Концепция стандартного прыжка Виета является доказательством от противного и состоит из следующих трех шагов:${}^{[1]}$

  1. Предположим к противоречию, что существует какое-то решение, которое нарушает данные требования.
  2. Возьмем минимальное такое решение согласно некоторому определению минимальности.
  3. Покажите, что отсюда следует существование меньшего решения; противоречие.

пример

Проблема №6 в IMO 1988: Пусть $a$ и $b$ натуральные числа такие, что $ab + 1$ разделяет $a^2 + b^2$. Докажи это$\frac{a^2 + b^2}{ab + 1}$ идеальный квадрат.${}^{[2]}$${}^{[3]}$

  1. Зафиксируйте некоторую ценность $k$это положительное целое число, не являющееся квадратом. Предположим, что существуют натуральные числа$(a, b)$ для которого $k = \frac{a^2 + b^2}{ab + 1}$.
  2. Позволять $(A, B)$ быть натуральными числами, для которых $k = \frac{A^2 + B^2}{AB + 1}$ и такой, что $A + B$ сводится к минимуму, и без ограничения общности полагаем $A \ge B$.
  3. Фиксация $B$заменить $A$ с переменной $x$ уступить $x^2 – (kB)x + (B^2 – k) = 0$. Мы знаем, что один из корней этого уравнения равен$x_1 = A$. По стандартным свойствам квадратных уравнений мы знаем, что другой корень удовлетворяет$x_2 = kB – A$ и $x_2 = \frac{B^2 – k}{A}$.
  4. Первое выражение для $x_2$ показывает, что $x_2$ является целым числом, а из второго выражения следует, что $x_2 \ne 0$ поскольку $k$не идеальный квадрат. Из$\frac{x_2^2 + B^2}{x_2B + 1} = k > 0$ далее следует, что $x_2$положительное целое число. В заключение,$ A \ge B$ подразумевает, что $x_2 = \frac{B^2 − k}{A} < A$ и поэтому $x_2 + B < A + B$, что противоречит минимальности $A + B$.
1 twentyyears Aug 17 2020 at 15:17

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

Минимальность $A+B$противоречит. (2) и (3) не имеют отношения к$k$. (4) говорит$x$ не может быть $0$ если $k$не идеальный квадрат. Так$x\neq 0$. Но если$x\neq 0$, чисто через алгебру, независимо от $k$квадратные или нет, мы противоречим минимальности. Итак, суть,$(A,B)$ сводит к минимуму $A+B$. только если$x_2=0$. Поскольку нет минимума$(A,B)$ пары, когда $k$ не квадрат, можно заключить, что таких пар нет.

Счел ли Атанасов это настолько тривиальным, что держал это в своей голове, остается загадкой.