Апология математики (сборник статей)

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

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

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

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

Пример 9. По условиям шахматного турнира каждый участник должен сыграть с каждым другим одну партию. Докажите, что в любой момент турнира найдутся два шахматиста, сыгравшие к этому моменту одинаковое число партий.

Решение. Пусть всего в турнире участвует n шахматистов. Не будем их беспокоить и заменим каждого игрока карточкой с его именем. Каждый игрок мог сыграть от 0 до n – 1 партий, так что для каждого игрока имеется n вариантов. Приготовим столько ящиков, сколько есть вариантов, и пронумеруем их от 0 до n – 1. В ящик с номером k положим карточки с именами тех игроков, которые к данному моменту сыграли k партий. Наша задача – доказать, что хотя бы в одном ящике лежит не менее двух карточек.

Возможны два случая.

Первый случай: каждый игрок сыграл хотя бы одну партию. Тогда ящик № 0 пустой и для размещения n карточек остаётся n – 1 ящиков с номерами от 1 до n – 1.

Второй случай: есть игрок, не сыгравший ни одной партии. Его карточка попадает в ящик № 0, но зато ящик № n – 1 оказывается пустым, потому что нет игрока, сыгравшего со всеми другими игроками; для размещения n карточек остаётся n – 1 ящиков с номерами от 0 до n – 2.

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

§ 5. Доказательства от противного

Доказательства от противного выстраивают так. Делают предположение, что верно утверждение B, противное, т. е. противоположное, тому утверждению A, которое требуется доказать, и далее, опираясь на это B, приходят к противоречию; тогда заключают, что, значит, B неверно, а верно A.