Владимир Успенский – Апология математики (сборник статей) (страница 62)

§ 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 и подставляя их в уравнение, убеждаемся, что ни одно из них не обращает в ноль левую часть. Это есть типичное доказательство методом перебора.

«Зачем же поступать так странно?!» – возмутится читатель. Ведь достаточно опереться на следующее свойство произведения: если произведение равно нолю, то непременно равен нолю хотя бы один из сомножителей; действительно, из указанного свойства вытекает, что если число является корнем нашего уравнения, то оно есть либо 2008, либо 3, либо 216, либо 548, а из этих четырёх чисел только 3 и 216 одновременно неотрицательны и меньше, чем 420. Читатель совершенно прав: его доказательство короче. Однако мы призываем читателя осознать тот факт, что предложенное нами доказательство совершенно убедительно, а значит, совершенно безупречно. Кроме того, наше доказательство хотя и длиннее, но в определённом смысле проще: ведь оно не предполагает использования указанного выше свойства произведения. Представьте себе, что это свойство кому-либо неизвестно; тогда этот «кто-либо» поймёт наше доказательство, но не поймёт доказательства читателя. Мы преследовали и ещё одну, практическую, цель: приучить читателя не бояться доказательств методом перебора. Ведь хотя доказательство методом перебора может потребовать намного больше времени, чем какое-нибудь хитроумное короткое доказательство, поиск последнего способен затянуться надолго…

Пример 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, а то и пытаться самому сочинить такое доказательство?

§ 4. Косвенные доказательства существования. принцип дирихле

Самый естественный способ доказать, что объект с заданными свойствами действительно существует, – это его указать, назвать, построить (и, разумеется, убедиться, что он действительно обладает нужными свойствами). Чтобы доказать, например, что данное уравнение имеет решение, достаточно указать какое-то его решение. Такие доказательства существования чего-нибудь называются прямыми, или конструктивными. Прямыми будут, например, приводимые в примерах 17 и 18 доказательства существования несоизмеримых отрезков, поскольку такая пара отрезков будет там указана.

Но бывают и косвенные доказательства, когда обоснование того факта, что искомый объект существует, происходит без прямого указания такого объекта.

Пример 6. В некоторой шахматной партии противники согласились на ничью после 15-го хода белых. Доказать, что какая-то из чёрных фигур ни разу не передвигалась с одного поля доски на другое. (Термин «фигура» понимается здесь в широком смысле, включающем и пешки.)

Рассуждаем так. Передвижения чёрных фигур по доске происходят лишь при ходах чёрных. Если такой ход не есть рокировка, передвигается одна фигура; если же ход есть рокировка, передвигаются две фигуры. Чёрные успели сделать 14 ходов, и лишь один из них мог быть рокировкой. Поэтому самое большое количество чёрных фигур, затронутых ходами, есть 15. А всего чёрных фигур 16. Значит, по крайней мере одна из них не участвовала ни в каком ходе чёрных. Отметим, что здесь мы не указываем такую фигуру конкретно (мы могли бы это сделать лишь в том случае, если бы наблюдали шахматную партию или располагали её записью), а лишь доказываем, что она непременно существует.

Пример 7. В самолёте летит 380 пассажиров. Доказать, что какие-то два из них отмечают свой день рождения в один и тот же день года.

Рассуждаем так. Всего имеется 366 (включая 29 февраля) возможных дат для празднования дня рождения. А пассажиров больше; значит, не может быть, чтобы у всех у них дни рождения приходились на различные даты, и непременно должно быть так, что какая-то дата является общей по крайней мере для двух человек. Ясно, что этот эффект будет обязательно наблюдаться, начиная с числа пассажиров, равного 367. А вот если это число равно 366, не исключено, что числа и месяцы их дней рождения будут для всех различны, хотя это и чрезвычайно маловероятно. (Кстати, теория вероятностей учит, что если случайно выбранная группа людей состоит более чем из 22 человек, то более вероятно, что у кого-нибудь из них дни рождения будут совпадать, нежели что у всех у них дни рождения приходятся на разные дни года.)

Логический прием, применённый нами в примере 7, носит название принцип Дирихлé – по имени знаменитого немецкого математика XIX в. Петера Густава Лежёна Дирихлé. Вот общая формулировка этого принципа:

Если имеется n ящиков, в которых находится в общей сложности по меньшей мере n + 1 предметов, то непременно найдётся ящик, в котором лежат по меньшей мере два предмета.

Чтобы увидеть, как приведённая формулировка используется в примере 7, надо мысленно представить себе 366 ящиков и надписать на каждом одну из 366 дат года, а затем мысленно же разместить по ящикам 380 пассажиров, помещая каждого пассажира в ящик с соответствующей этому пассажиру датой (всё делается только мысленно, так что никакой дискомфорт пассажирам не грозит). Тогда в каком-то из ящиков окажется более одного пассажира, и у этих пассажиров будет общий день рождения.

Пример 8. Докажите, что если прямая не проходит ни через одну из вершин треугольника, то она не может пересекать все его стороны.

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