Глава

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

Бесконечный спуск, леммы о чётности, минимальные контрпримеры, примитивные решения и противоречие через меньшее решение.

Назад к курсу Практика Лестницы
Теория Примеры Практика Лестницы

Теория

1. Главная идея

Бесконечный спуск - это метод доказательства. Мы предполагаем, что существует положительное целочисленное решение, а затем строим меньшее положительное решение того же типа. Повторять это бесконечно невозможно, потому что положительные целые числа не могут бесконечно убывать.

Типичная схема:

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

2. Спуск и четность

Многие спуски начинаются с четности. Если \(x^2\) четно, то \(x\) четно. Это может заставить обе переменные делиться на \(2\), после чего деление дает меньшее решение.

3. Пример: \(x^2=2y^2\)

Пусть уравнение \(x^2=2y^2\) имеет ненулевое целое решение. Тогда \(x^2\) четно, значит \(x=2k\). Подставляем:

\[ 4k^2=2y^2,\qquad y^2=2k^2. \]

Значит, \(y\) тоже четно. Обе переменные четны, и после деления на \(2\) получается меньшее решение. Так можно повторять бесконечно, что невозможно. Поэтому единственное целое решение - \((0,0)\).

4. Минимальный контрпример

Часто мы предполагаем, что существует наименьший контрпример. Если из него получается меньший контрпример, исходный не мог существовать.

5. Спуск в олимпиадных задачах

Бесконечный спуск часто появляется, когда:

  • уравнение заставляет все переменные иметь общий делитель;
  • минимальное решение можно превратить в меньшее;
  • четность или остатки повторяются после масштабирования;
  • "наименьший" объект порождает еще меньший объект.

Примеры

Пример 1. Четный квадрат

Эта лемма постоянно используется в задачах на спуск.

Задача. Докажите: если \(n^2\) четно, то \(n\) четно.
Решение. Если \(n\) нечетно, то \(n=2k+1\). Тогда \(n^2=4k^2+4k+1\), что нечетно. Поэтому если \(n^2\) четно, то \(n\) не может быть нечетным, значит \(n\) четно.

Пример 2. Первый спуск

Это модельное доказательство спуском для всего модуля.

Задача. Докажите, что единственное целое решение уравнения \(x^2=2y^2\) - это \((0,0)\).
Решение. Пусть существует ненулевое решение. Так как \(x^2=2y^2\), число \(x^2\) четно, значит \(x=2k\). Тогда \(4k^2=2y^2\), откуда \(y^2=2k^2\), значит \(y\) четно. Обе переменные четны, и после деления на \(2\) получаем меньшее ненулевое решение. Бесконечно повторять это невозможно. Значит, подходит только \((0,0)\).

Пример 3. Иррациональный корень

Явно проговорите, что несократимость означает отсутствие общего делителя.

Задача. Используйте бесконечный спуск, чтобы доказать, что \(\sqrt2\) иррационально.
Решение. Если \(\sqrt2=a/b\), то \(a^2=2b^2\). По идее предыдущего спуска \(a\) и \(b\) должны быть четными. Это противоречит несократимости дроби. Поэтому \(\sqrt2\) иррационально.

Пример 4. Спуск по тройке

Используйте это, чтобы обобщить идею спуска с \(2\).

Задача. Докажите, что единственное целое решение уравнения \(x^2=3y^2\) - это \((0,0)\).
Решение. Если \(x^2=3y^2\), то \(3\mid x^2\), значит \(3\mid x\). Пусть \(x=3k\). Тогда \(9k^2=3y^2\), откуда \(y^2=3k^2\), значит \(3\mid y\). Деление обеих переменных на \(3\) дает меньшее ненулевое решение, что невозможно по спуску. Поэтому подходит только \((0,0)\).

Пример 5. Нет суммы квадратов

Это первый спуск с тремя переменными в курсе.

Задача. Докажите, что единственное целое решение уравнения \(x^2+y^2=3z^2\) - это \((0,0,0)\).
Решение. По модулю \(3\) правая часть равна \(0\). Так как квадраты дают только \(0\) и \(1\), равенство \(x^2+y^2\equiv0\pmod3\) возможно только при \(x^2\equiv y^2\equiv0\pmod3\). Значит, \(3\mid x\) и \(3\mid y\). Тогда из уравнения следует и \(3\mid z\). Делим все переменные на \(3\) и получаем меньшее ненулевое решение, что невозможно. Значит, только \((0,0,0)\).

Пример 6. Минимальный контрпример

Это логическая основа метода.

Задача. Объясните, почему не может существовать непустое множество положительных целых чисел без наименьшего элемента.
Решение. Положительные целые числа вполне упорядочены: любое непустое множество положительных целых чисел имеет наименьший элемент. Бесконечный спуск использует эту идею: если из каждого предполагаемого элемента получается меньший положительный элемент, такого множества не существует.

Пример 7. Цепочка спуска

Эта абстрактная задача помогает ученикам увидеть скелет доказательства.

Задача. Пусть положительное целое число \(n\) обладает свойством \(P\), и из любого положительного числа со свойством \(P\) получается меньшее положительное число со свойством \(P\). Докажите, что ни одно положительное число не обладает свойством \(P\).
Решение. Если такие числа существуют, выберем наименьшее, скажем \(n\). По условию из \(n\) получается меньшее положительное число со свойством \(P\), что противоречит минимальности \(n\). Поэтому таких положительных чисел нет.

Пример 8. Делимость на все степени

Это обосновывает фразу делится на сколь угодно большие степени.

Задача. Докажите: если целое число \(n\) делится на \(2^k\) для любого положительного целого \(k\), то \(n=0\).
Решение. Если \(n\ne0\), выберем \(k\) так, что \(2^k>|n|\). Ненулевое кратное \(2^k\) по модулю не меньше \(2^k\), что невозможно при \(|n|<2^k\). Значит, \(n=0\).

Задачи

Задачи

Пока нет опубликованных задач.

Лестницы

Опубликованных лестниц пока нет.
Предыдущая глава
Следующая глава