D4 Бесконечный спуск

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

Метод придуман Пьером де Ферма в XVII веке специально для доказательства отсутствия целочисленных решений у диофантовых уравнений. Именно с его помощью Ферма доказал, что $x^4 + y^4 = z^2$ не имеет решений в натуральных числах.

Интуиция: представь, что тебя просят найти наименьшее натуральное число, которое «нарушает» некоторое свойство. Если из любого такого числа можно построить ещё меньшее нарушителя — ни один нарушитель не существует. Это похоже на то, как если бы каждый найденный преступник немедленно указывал на меньшего — значит, всю цепочку начать невозможно.

Структура доказательства всегда одинакова: (1) предположить существование наименьшего решения $(x_0, y_0, \ldots)$; (2) провести алгебраические преобразования и показать, что существует решение $(x_1, y_1, \ldots)$ с той же структурой, но $x_1 < x_0$ (или по другой мере); (3) зафиксировать противоречие с минимальностью. Метод — разновидность доказательства от противного, усиленная принципом наименьшего числа.

• Принцип наименьшего числа (ПНЧ): каждое непустое подмножество натуральных чисел имеет наименьший элемент. Условие: работаем с натуральными числами (или целыми, ограниченными снизу$). *$Когда использовать:* основа метода — противоречие с ПНЧ завершает доказательство.

• Параметризация пифагоровых троек: все примитивные натуральные решения $x^2 + y^2 = z^2$ имеют вид $x = m^2 - n^2$, $y = 2mn$, $z = m^2 + n^2$ при $m > n > 0$, $\gcd(m,n)=1$, $m \not\equiv n \pmod{2}$. Когда использовать: при доказательстве невозможности уравнений типа $x^4 + y^4 = z^2$ — первый шаг это параметризация.

• Принцип Ферма для $x^4 + y^4 = z^2$: если $(x,y,z)$ — примитивное решение, параметризация сводит задачу к уравнению вида $a^4 + b^4 = c^2$ с меньшим значением $z$. Когда использовать: ключевой пример применения спуска для степеней $\geq 4$.

• Выбор меры убывания. Определи натуральную величину $f(x,y,\ldots) > 0$ (обычно наибольший из аргументов, или $x+y+z$, или $z$ в уравнении $\ldots = z^k$), которая строго убывает при «спуске».

• Параметризация решений. Если условие задачи позволяет, параметризуй все решения (как в случае пифагоровых троек) и ищи, как параметры нового решения соотносятся со старыми.

• Анализ чётности и делимости. Часто спуск начинается с наблюдения: если решение существует, то все аргументы чётные → можно поделить на 2 → получили меньшее решение.

• Переход к примитивному решению. Предполагай, что $\gcd(x,y,z)=1$ (примитивное решение). Если из него строится другое примитивное меньшее — противоречие с минимальностью.

• Алгебраические тождества для спуска. Разложи выражение через тождества (сумма квадратов, разность кубов) так, чтобы выявить новое решение меньшего размера.

Поверхностные признаки (что буквально написано):
- «Докажите, что уравнение $f(x,y,z)=0$ не имеет натуральных/целых решений»
- «Докажите, что $\sqrt{2}$, $\sqrt[3]{5}$ и подобные числа иррациональны»
- В задаче фигурируют высокие степени ($x^4$, $x^4 + y^4$, $x^3 + y^3$)

Структурные признаки (форма выражения, объекты):
- Уравнение однородное по степени: если $(x,y,z)$ — решение, то $(kx, ky, kz)$ тоже
- Предположение о решении автоматически даёт делимость всех переменных на некоторое $d > 1$ - Сравнения по модулю дают необходимое условие «все переменные чётные» или «все делятся на 3»

Цель задачи (что от тебя хотят):
- Доказать, что множество решений пусто
- Доказать иррациональность числа
- Доказать, что уравнение имеет только «тривиальное» решение $(0,0,0)$

Задача 1. Докажите, что уравнение $x^4 + y^4 = z^2$ не имеет решений в натуральных числах.

Источник: Ферма, XVII в.; классика олимпиадной теории чисел

Как думать (рассуждение ученика$):
1. $Что вижу?* Степень 4 слева, степень 2 справа — похоже на «пифагорово» уравнение, но с $x^4 = (x^2)^2$. Это сумма двух полных квадратов, равная квадрату. Попробую параметризовать как пифагорову тройку!$2. *$Почему спуск? Если параметризация сводит к меньшему решению того же вида — это классический спуск.$3. *$Какой первый ход?* Предположу, что $(x, y, z)$ — примитивное решение (НОД = 1) с минимальным $z$.

Решение:

Предположим, что $(x, y, z)$ — примитивное натуральное решение $x^4 + y^4 = z^2$ с минимальным $z$.

Запишем $(x^2)^2 + (y^2)^2 = z^2$ — это примитивная пифагорова тройка. По параметризации (при условии, что $y^2$ чётное):$$x^2 = m^2 - n^2, \quad y^2 = 2mn, \quad z = m^2 + n^2,$$ где $m > n > 0$, $\gcd(m,n)=1$, $m \not\equiv n \pmod{2}$.

Из $y^2 = 2mn$ и $\gcd(m,n)=1$, $m$ чётное, $n$ нечётное: $m = 2s^2$, $n = t^2$. Из $x^2 = m^2 - n^2 = (m-n)(m+n)$ и взаимной простоты снова получаем пифагорову тройку.

Из уравнения $n^2 + (x^2) \cdot \ldots$ получаем, что $s$ и $t$ удовлетворяют уравнению $s^4 + t^4 = r^2$ с $r = m < z$. Это противоречит минимальности $z$.

Ответ: уравнение $x^4 + y^4 = z^2$ не имеет решений в натуральных числах.

Что в этой задаче было главным: связка «параметризация пифагоровых троек → новое решение того же уравнения с меньшим параметром» — это и есть бесконечный спуск в чистом виде.

Задача 2. Докажите, что $\sqrt{2}$ иррационально методом спуска.

Источник: тренировочная (иллюстрация метода)

Как думать (рассуждение ученика$):
1. $Что вижу?* Надо доказать иррациональность — $\sqrt{2} \neq p/q$ для целых $p, q$. Покажем спуском.$2. *$Как строить спуск? Если $\sqrt{2} = p/q$, то $p^2 = 2q^2$. Значит $p$ чётно, $p = 2k$, тогда $4k^2 = 2q^2$, $q^2 = 2k^2$ — получили меньшее решение!

Решение:

Предположим, что $p^2 = 2q^2$ для натуральных $p, q$ с минимальным $p$. Тогда $p^2$ чётно, значит $p$ чётно: $p = 2k$. Подставим: $4k^2 = 2q^2$, то есть $q^2 = 2k^2$. Пара $(q, k)$ — тоже решение, и $q < p$ (так как $q^2 = 2k^2 < 2q^2 = p^2$). Противоречие с минимальностью $p$.

Ответ: $\sqrt{2}$ иррационально.

Что в этой задаче было главным: любое предполагаемое решение немедленно порождает строго меньшее — цепочка не имеет начала, значит решений нет.

• Ошибка: начать спуск без фиксации минимального решения. → Почему неверно: спуск доказывает противоречие именно с минимальностью; если её не зафиксировать, аргумент не работает. → Как избежать: всегда начинай с «пусть $(x_0, y_0, \ldots)$ — решение с минимальным $x_0$ (или другой мерой)».

• Ошибка: «меньшее решение» уменьшается, но не строго ($x_1 \leq x_0$ вместо $x_1 < x_0$). → Почему неверно: если возможно равенство, противоречие с минимальностью не возникает. → Как избежать: явно показывай строгое неравенство меры.

• Ошибка: забыть проверить, что «меньшее решение» действительно является решением того же уравнения. → Почему неверно: спуск работает только если новый объект имеет то же свойство. → Как избежать: подставь $(x_1, y_1, \ldots)$ в уравнение и убедись, что оно выполнено.

• Ошибка: применять спуск к задачам, где мера не натуральная (например, рациональные числа могут убывать бесконечно). → Почему неверно: ПНЧ работает только для натуральных чисел (или целых, ограниченных снизу). → Как избежать: убедись, что мера принимает натуральные значения.

• Ошибка: путать спуск с индукцией. → Почему неверно: в индукции мы строим решение для $n+1$ из решения для $n$; в спуске мы приходим к противоречию, строя меньшее решение из предполагаемого наименьшего. → Как избежать: помни: спуск — доказательство от противного, индукция — конструктивна.