§ 3. Доказательства методом перебора

Пример 1. Доказать, что среди целых неотрицательных чисел, меньших числа 420, нет других корней уравнения (x + 2008) (x – 3) (x – 216) (x – 548) = 0, кроме чисел 3 и 216.

Доказательство: Последовательно перебирая числа 0, 1, 2, 4, 5, 6, 7, …, 213, 214, 215, 217, 218, 219, …, 417, 418, 419 и подставляя их в уравнение, убеждаемся, что ни одно из них не обращает в ноль левую часть. Это есть типичное доказательство методом перебора.

Пример 2. Доказать, что среди трёхзначных чисел нет числа, делящегося одновременно на 7, 11 и 13.

Школьник младших классов, знакомый лишь с делением, может справиться с этой задачей, перебрав и испробовав все 900 трёхзначных чисел. Школьник старших классов знает (точнее, должен знать), что среди натуральных чисел выделяются простые числа и что простым называется всякое натуральное число, которое, во-первых, больше единицы и, во-вторых, делится только на 1 и на само себя. Так что числа 7, 11 и 13 – простые. А ежели школьник ещё более образован, то он знает, что число, делящееся на каждое из нескольких простых чисел, обязано делиться и на их произведение. Произведение 7 × 11 × 13 равно 1001. Но никакое трёхзначное число не может делиться на 1001.

Пример 3. Представим себе, что мы выдвинули такую гипотезу: уравнение x⁴ + y⁴ = z² не имеет решения в области целых положительных чисел, не превосходящих числа 100.

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

Первый способ. Перебрать все десять тысяч пар 〈x, y〉, таких что 1 ≤ x ≤ 100, 1 ≤ y ≤ 100; возвести для каждой такой пары её члены в четвёртую степень, сложить и убедиться, что сумма не является полным квадратом.

Второй способ. Попытаться самостоятельно получить доказательство теоремы о неразрешимости уравнения.

Второй способ труден, первый способ скучен. Конечно, можно поручить осуществление первого способа компьютеру; однако ведь можно взять вместо верхней границы 100 другую, настолько большýю, что и компьютеру перебор будет не под силу.

Сейчас мы приведём реальный пример перебора, с которым не в состоянии справиться современные компьютеры.

Пример 4. В 1742 г. российский математик Христиан Гольдбах выдвинул такую гипотезу: всякое натуральное число n, начиная с 6, есть сумма трёх простых чисел. Для небольших n гипотезу Гольдбаха можно проверить непосредственно; например, 96 = 2 + 47 + 47. С другой стороны, для очень больших нечётных чисел гипотеза тоже верна: как доказал в 1937 г. И. М. Виноградов, гипотеза Гольдбаха верна для всех нечётных чисел n, бóльших некоторого громадного n₀. Что касается самого этого n₀, то из результатов Виноградова и его последователей вытекает, что в качестве n₀ можно взять, например, число 3^{14 348 907}, требующее свыше 6,5 млн знаков для своей десятичной записи. Оставалось, таким образом, проверить все нечётные числа от 7 до названного числа, и тогда для нечётных чисел гипотеза Гольдбаха оказалась бы либо доказанной, либо опровергнутой. Однако такая проверка совершенно нереальна. В 2013 г. перуанский математик Харальд Хельфготт доказал, что не только очень большие, но любые нечётные числа, начиная с 7, представимы в виде суммы трёх простых чисел. Тем самым проблема Гольдбаха была решена для нечётных чисел.

Пример 5. Целые числа вида n² + 1 обладают следующим свойством: у них не бывает простых делителей вида 4k + 3.

Если перед читателем встанет задача проверить это свойство для предъявленного ему множества (в другом варианте – для одного, но большого числа вида n² + 1), то что он предпочтёт: решать задачу перебором или же искать в математической литературе доказательство общей теоремы относительно чисел вида n² + 1, а то и пытаться самому сочинить такое доказательство?

Отправить