Пример 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.
Пример 10. Этот пример встречается и в «Началах» Евклида, и в современных школьных учебниках. Пусть дан треугольник и два его неравных угла. Требуется доказать утверждение A: против большего угла лежит бóльшая сторона.
Делаем противоположное предположение B: сторона, лежащая в нашем треугольнике против большего угла, меньше или равна стороне, лежащей против меньшего угла. Предположение B вступает в противоречие с ранее доказанной теоремой о том, что в любом треугольнике против равных сторон лежат равные углы, а если стороны неравны, то против большей стороны лежит больший угол. Значит, предположение B неверно, а верно утверждение А. Интересно, что прямое (т. е. не «от противного») доказательство теоремы A оказывается намного более сложным.
Пример 11. Иррациональность квадратного корня из двух. Арифметическое доказательство. Обозначим этот корень буквой r и начнём рассуждать от противного. Итак, число r рационально и таково, что r² = 2. Всякое рациональное число выражается дробью. Все выражающие число r дроби равны друг другу. Среди них найдётся несократимая дробь – доказательство этого простого факта составляет предмет примера 15. Пусть эта дробь есть m/n. Следовательно,
Освобождаясь от знаменателя, получаем:
Мы видим, что число m2 чётно. Но квадрат любого нечётного числа всегда нечётен; значит, число m чётно, m = 2k при некотором целом k. Подставляя 2k в формулу (1) вместо m, получаем:
и после сокращения на 2
Совершенно так же, как мы убедились в чётности 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. Доказать, что для любых двух натуральных чисел существует наибольший общий делитель.
Поскольку мы договорились начинать натуральный ряд с единицы (а не с ноля), то все делители любого натурального числа не превосходят самого этого числа и, следовательно, образуют конечное множество. Для двух чисел множество их общих делителей (т. е. таких чисел, каждое из которых является делителем для обоих рассматриваемых чисел) тем более конечно. Найдя среди них наибольшее, получаем требуемое.
Пример 15. Доказать, что среди всех равных друг другу дробей непременно найдётся несократимая дробь.
Первое доказательство – со ссылкой на пример 14, а следовательно, с косвенным использованием принципа наибольшего числа. В нашем множестве дробей выберем произвольную дробь и найдём наибольший общий делитель d её числителя и знаменателя. Если d = 1, то выбранная нами дробь уже несократима. Если d ≠ 1, то сократим её числитель и знаменатель на это число d. Полученная дробь будет несократимой. Ведь если бы её можно было бы ещё сократить на какое-то число q, то произведение dq, большее числа d, было бы делителем числителя и знаменателя первоначальной дроби и d не было бы наибольшим общим делителем.
Второе доказательство – с использованием принципа наименьшего числа. Рассмотрим множество натуральных чисел, к которому отнесём всякое число, являющееся знаменателем какой-нибудь из дробей нашей коллекции равных дробей. Найдём в этом множестве наименьшее число. Дробь с таким знаменателем будет несократима, потому что при любом сокращении и числитель, и знаменатель уменьшаются.
Третье доказательство – с использованием второй формулировки принципа наименьшего числа. Предположим, что в нашем множестве дробей нет несократимой. Возьмём произвольную дробь из этого множества и сократим её. Полученную тоже сократим и т. д. Знаменатели этих дробей будут всё меньшими и меньшими, и возникнет бесконечная убывающая последовательность натуральных чисел, что невозможно.
Продемонстрированный в третьем доказательстве примера 15 вариант метода от противного, когда возникающее противоречие состоит в появлении бесконечной последовательности убывающих натуральных чисел (чего, повторим, быть не может), называется методом бесконечного (или безграничного) спуска.
Пример 16. Вот ещё пример на метод бесконечного спуска. Выше, говоря о методе перебора, мы упомянули, что уравнение x4 + y4 = z2 не имеет решений в области натуральных чисел. Стандартный способ доказательства этого факта состоит в доказательстве от противного: противоречие выводится из предположения, что существует тройка (а, b, с) натуральных чисел, являющаяся решением уравнения, т. е. такая, что a4 + b4 = c2. Для получения требуемого противоречия применяют метод бесконечного спуска. Мы не будем здесь излагать, как именно осуществляется описываемое ниже построение[139], а ограничимся общей идеей. Идея же состоит в том, что указывается способ, следуя которому для каждой тройки натуральных чисел (а, b, с), служащей решением нашего уравнения, строится другая тройка натуральных чисел (а´, b´, с´), также служащая решением того же уравнения, но такая, что |с´| < |c|. Применяя этот метод, для тройки решения (а´, b´, с´) можно построить тройку-решение (а´´, b´´, с´´), а для этой последней – тройку (а´´´, b´´´, с´´´) и т. д. А тогда возникает невозможная убывающая последовательность натуральных чисел |c| > |c´| > |с´´| > |c´´´| >….
