участвует 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.

Пример 10. Этот пример встречается и в «Началах» Евклида, и в современных школьных учебниках. Пусть дан треугольник и два его неравных угла. Требуется доказать утверждение A: против большего угла лежит бóльшая сторона.

Делаем противоположное предположение B: сторона, лежащая в нашем треугольнике против большего угла, меньше или равна стороне, лежащей против меньшего угла. Предположение B вступает в противоречие с ранее доказанной теоремой о том, что в любом треугольнике против равных сторон лежат равные углы, а если стороны неравны, то против большей стороны лежит больший угол. Значит, предположение B неверно, а верно утверждение А. Интересно, что прямое (т. е. не «от противного») доказательство теоремы A оказывается намного более сложным.

Пример 11. Иррациональность квадратного корня из двух. Арифметическое доказательство. Обозначим этот корень буквой r и начнём рассуждать от противного. Итак, число r рационально и таково, что r² = 2. Всякое рациональное число выражается дробью. Все выражающие число r дроби равны друг другу. Среди них найдётся несократимая дробь – доказательство этого простого факта составляет предмет примера 15. Пусть эта дробь есть m/n. Следовательно,

(m/n)² = 2.

Освобождаясь от знаменателя, получаем:

m² = 2n². (1)

Мы видим, что число m2 чётно. Но квадрат любого нечётного числа всегда нечётен; значит, число m чётно, m = 2k при некотором целом k. Подставляя 2k в формулу (1) вместо m, получаем:

(2k)² = 2n² (2)

и после сокращения на 2

2k² = n². (3)

Совершенно так же, как мы убедились в чётности m, убеждаемся в чётности n. Итак, оба числа m и n чётны, и дробь m/n можно сократить на 2, а ведь мы выбрали её несократимой. Полученное противоречие доказывает, что число r не может быть рациональным, оно иррационально.

Пример 12. Доказать, что уравнение x³ + x + 1 = 0 не имеет решений в рациональных числах.

Рассуждаем от противного. Предположим, что наше уравнение имеет рациональный корень. Запишем его в виде несократимой дроби p/q. Итак, p³/q³ + p/q + 1 = 0. Умножая обе части на q³, получаем равенство p³ + pq² + q³ = 0. Замечаем, что если хотя бы одно из чисел p и q нечётно, то нечётно и выражение p³ + pq³ + q³. Но этого не может быть, потому что оно равно нолю, а ноль – число чётное. Значит, числа p и q оба чётные, но этого тоже не может быть, потому что дробь p/q несократима.

Чаще всего способом от противного доказывают, что объекта с заданными свойствами не существует. В самом деле, если требуется доказать, что что-то существует, то можно просто предъявить соответствующий объект (конечно, надо ещё доказать, что предъявлено именно то, что надо, т. е. что предъявленный объект обладает требуемыми свойствами). А как доказать, что чего-то нет? Хорошо, если это «что-то» надо искать среди конечного количества элементов, тогда можно попробовать метод перебора. А если среди бесконечного? Один из методов, применяемых в этом случае, есть так называемый метод бесконечного спуска, речь о котором пойдёт ниже, в § 6, и который можно рассматривать как частный случай метода доказательства от противного.

§ 6. Принципы наибольшего и наименьшего числа и метод бесконечного спуска

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

Принцип наименьшего числа формулируется так: в любом непустом (а не только в конечном!) множестве натуральных чисел существует наименьшее число.

Вторая формулировка принципа наименьшего числа: не существует бесконечной убывающей (т. е. такой, в которой каждый последующий член меньше предыдущего) последовательности натуральных чисел.

Эти две формулировки принципа наименьшего числа равносильны. В самом деле, если бы существовала бесконечная убывающая последовательность натуральных чисел, то среди членов этой последовательности не существовало бы наименьшего. Теперь представим себе, что удалось найти множество натуральных чисел, в котором наименьшее число отсутствует; тогда для любого элемента этого множества найдётся другой, меньший, а для него – ещё меньший и т. д., так что возникает бесконечная убывающая последовательность натуральных чисел.

Принцип наибольшего числа и обе формулировки принципа наименьшего числа с успехом применяются в доказательствах. Продемонстрируем это на примерах 13–15.

Пример 13. Доказать, что любое натуральное число, большее единицы, имеет простой делитель.

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

Пример 14. Доказать, что для любых двух натуральных чисел существует наибольший общий делитель.

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