С методом доказательства от противного каждый школьник неизбежно сталкивается (неожиданно, и поэтому, порой, жестко) на уроках геометрии. Надеемся, что ученик, разобравшийся с материалом предыдущих занятий, воспримет метод от противного как естественное продолжение знакомства с логикой и будет избавлен от неуместных формальных трудностей при изучении геометрии.

Задача 7.1 служит вводным упражнением, показывающим логическую основу метода от противного. С формальной точки зрения он состоит в замене доказательства того, что из А следует Б, на доказательство того, что из «не Б» следует «не А». Как показывает задача 7.2, иногда такой простой трюк существенно облегчает задачу.

Однако настоящая мощь метода от противного проявляется при более широком его понимании. Пусть дано А, а доказать требуется Б. Предположив противное, мы получим уже два условия: А и «не Б», а с двумя условиями работать легче, чем с одним. Из них требуется получить два любых противоречащих друг другу высказывания: В и «не В». Задачи 7.2, 7.3 и 7.4 демонстрируют, что В может как совпадать с одним из условий А или Б, так и быть новым утверждением.

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

Задача на доказательство не всегда содержит слово «докажите». Иногда решающий должен сам выбрать верный ответ на вопрос типа «Можно ли…», «Существует ли…» ит. п., а потом доказать правильность ответа. Если ответ отрицательный, часто бывает удобно предположить, что он положительный, а затем прийти к противоречию. Такое рассуждение от противного применяется в задачах 7.6 и 7.11, а также ДЗЗ и Д36.

Немного рекламы.

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

2) «Противное» часто оказывается хорошим. От противного удобно доказывать «отрицательные» качества: неделимость, иррациональность, бесконечность. А предположив противное, мы сразу получим что-то хорошее, с дополнительными свойствами (делимость на простое число, числитель и знаменатель рациональной дроби, размер конечного множества).

3) Метод от противного не помешает даже там, где он не нужен. Пусть дано А, и из этого без всякого «противного» можно доказать Б. Но мы этого не заметили и зачем-то предположили «не Б». И только после этого из А (без использования «не Б») получили Б. Вот и хорошо! Б и «не Б» противоречат друг другу, метод от противного сработал.

А теперь антиреклама.

1) Если метод от противного сработал описанным только что образом, самое время упростить доказательство и выбросить из него «противную» оболочку.

2) Недостаток логической культуры может привести к некорректному «доказательству» от противного. Одна из целей этого занятия, да и всей книжки – научить, как таких ошибок избегать. В частности, задача 7.5 еще раз напоминает о неравносильности обратных друг другу высказываний.

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

Задача 7.1. Если рыцарь встречает дракона, то рыцарь вступает в бой.

1) Составьте к этому высказыванию обратное, противоположное и противоположное обратному.

2) Известно, что рыцарь вступил в бой. Означает ли это, что он встретил дракона?

3) Рыцарь не вступил в бой. Означает ли это, что он не встретил дракона?

Ответ. 1) Обратное: если рыцарь вступает в бой, то рыцарь встречает дракона. Противоположное: если рыцарь не встречает дракона, то рыцарь не вступает в бой. Противоположное обратному: если рыцарь не вступает в бой, то рыцарь не встречает дракона.

2) Не означает. Рыцарь мог вступить в бой не только с драконом. Например, с ветряными мельницами. Как мы не раз убеждались, истинность прямого и обратного высказывания никак не связаны.

3) Означает. Ведь если бы он встретил дракона, то вступил бы в бой, что противоречит условию. То есть истинному прямому высказыванию соответствует истинное высказывание, противоположное обратному. А это значит, что их можно заменять друг на друга.

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

Обсуждение. Как подступиться к этой задаче? Чисел без повторяющихся цифр много, и общие выводы делать о них затруднительно. Попробуем вместо прямой задачи решить противоположную обратной: докажем, что число, являющееся произведением двух чисел, состоящих только из единиц и нулей, содержит повторяющиеся цифры.

Решение. Предположим, что число является произведением двух чисел, состоящих только из единиц и нулей. Что может быть его последней цифрой? Только 1 или 0. А последней ненулевой цифрой? Только 1 (потому что произведение последних ненулевых цифр сомножителей – это произведение двух единиц). А что может быть первой цифрой? Тоже только 1. Однако по условию число не может содержать двух единиц. Значит, первая единица и является последней ненулевой цифрой. В таком случае в каждом из сомножителей только одна единица в записи. Но так как оба числа больше 1 (иначе другое равно произведению), оба они заканчиваются на 0, и в произведении найдутся два нуля.

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

Задача 7.3. Двое играют в «крестики-нолики» на бесконечной доске. Крестики ходят первыми. Выигрывает тот, кто смог поставить пять своих значков подряд по вертикали, горизонтали или диагонали. Докажите, что крестики могут как минимум не проиграть.

Обсуждение. Поясним, что значит «могут не проиграть». Вдруг крестики – первоклассник, а нолики – выпускник, игравший в «крестики-нолики» на всех уроках в течение одиннадцати лет? Однако в подобных задачах рассматривается игра не реальных людей, а идеальных игроков, способных просчитывать игру на какое угодно число ходов вперед. Исход партии между такими игроками предрешен правилами игры и не зависит от их настроения и самочувствия. Либо у идеальных крестиков есть беспроигрышная стратегия (т. е. возможность ходить так, чтобы не проиграть при любых действиях ноликов) – и тогда он ей непременно воспользуется и сможет не проиграть, либо нет, т. е. у ноликов есть возможность выигрывать всегда, независимо от ходов первого (то есть выигрышная стратегия).

Решение. Предположим противное. Пусть у первого игрока – крестиков – нет беспроигрышной стратегии. Это означает, что у второго есть выигрышная стратегия. В таком случае крестики могут сделать первый ход куда угодно, а затем руководствоваться выигрышной стратегией второго игрока. Если эта стратегия говорит ему поставить крестик туда, где он уже стоит, надо просто поставить его куда угодно, от этого хуже не будет. Таким образом, если выигрышная стратегия есть у ноликов, то она есть и у крестиков. Но у них не может быть одновременно выигрышных стратегий. Полученное противоречие показывает, что предположение неверно, и крестики при безошибочной игре не проиграют.

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

Задача 7.4. В клетках шахматной доски как-то расставлены все натуральные числа от 1 до 64. Докажите, что найдутся две соседние по стороне или по вершине клетки, числа в которых отличаются не меньше чем на 9.

Решение. Предположим противное: разность между числами, стоящими в любых двух соседних по стороне или вершине клетках, не превышает 8. Заметим, что расстояние между любыми двумя клетками не превышает семи королевских ходов. Поэтому разность между числами в любых двух клетках по предположению не превышает 7 · 8 = 56. Но разность 64 – 1 = 63 > 56. Полученное противоречие доказывает, что предположение неверно и найдутся два числа в соседних клетках, отличающиеся не менее чем на 9.

Комментарий. В этой задаче метод от противного применен в широком понимании: противоречащие друг другу утверждения («Числа в любых двух клетках отличаются не более чем на 56» и «Существуют две клетки, числа в которых отличаются на 63») не сформулированы явно ни в условии задачи, ни в предположении, а получены из них.

Задача 7.5. Острова архипелага связаны мостами так, что с каждого острова можно дойти до любого другого. Не более чем с двух островов ведет нечетное число мостов, а с остальных – четное. «Докажем», что можно обойти архипелаг, пройдя по каждому мосту ровно один раз.

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

Верно ли это «доказательство»?

Решение. Обозначим данное в задаче условие буквой А: «Не более чем с двух островов ведет нечетное число мостов, а с остальных – четное». То, что требуется доказать, обозначим как Б: «Можно прогуляться по архипелагу, пройдя по каждому мосту ровно один раз». Итак, требуется доказать А ⇒ Б. А что доказано? Что если «нечетных» островов хотя бы три, то обойти архипелаг, пройдя по разу по каждому мосту, нельзя. То есть доказано (вполне, кстати, верно) «не А» ⇒ * «не Б» – противоположное утверждение, которое, как уже обсуждалось в задаче 6.1, отнюдь не равносильно нужному. И неверна в доказательстве именно последняя фраза: «А если таких островов не более двух, то можно». Вот Б ⇒ А действительно равносильно «не А» ⇒ «не Б».

Комментарий. 1) Итак, слова «предположим противное» и «пришли к противоречию» сами по себе не являются магическим заклинанием. Распространенная ошибка – вместо требуемого утверждения доказать обратное ему. 2) Само утверждение про архипелаг верно, но доказывается сложнее, чем обратное.

Задача 7.6*. Конечно или бесконечно множество простых чисел?

Обсуждение. Не правда ли, вопрос естественный? Недаром его еще древние греки поставили. И он кажется очень сложным, не так ли? Во всяком случае, конечно ли множество пар простых чисел-близнецов (т. е. отличающихся друг от друга на 2), неизвестно до сих пор. Как не найдено и никакой формулы, позволяющей бесконечно вычислять одно простое число за другим. А некоторые простые по формулировке вопросы теории чисел решены весьма сложными современными методами (например, великая теорема Ферма или тернарная проблема Гольдбаха). Но вот вопрос о бесконечности множества простых чисел древние греки смогли не только поставить, но и решить. Приведем удивительное по красоте и простоте доказательство от противного, восходящее к «Началам» Евклида.

Решение. Пусть множество простых чисел конечно. Тогда можно выписать все простые числа: p1, p2, p3…, p n . Произведение всех этих чисел делится на каждое из них. А если его немножко «испортить», прибавив 1, то полученное число: p1p2p3… p n + 1 не будет делиться ни на одно из простых чисел p1, p2, p3…, p n . Можно ли это число разложить на простые множители? Если можно, то среди этих простых множителей нет известных нам чисел p1, p2, p3…, p n (то есть мы выписали не все простые числа!). А если нельзя, то это число само простое, причем большее всех выписанных нами чисел. В любом случае выписать все простые числа не удалось. Значит, их множество бесконечно.

Комментарий. Является ли приведенное доказательство доказательством от противного? Если да, то требовалось бы доказать, что из А следует Б. А мы вместо этого доказывали бы, что из «не Б» следует «не А». Но где же условие А? В задаче вообще ничего не дано!

Условие А появится, если переформулировать задачу так: «Пусть дано множество всех простых чисел. Доказать, что оно бесконечно». Предположив, что множество простых чисел конечно, мы убедились, что рассмотрели не все простые числа.

Метод от противного оказался эффективен, потому что помог от бесконечного количества, с которым непонятно что делать, перейти к конечному, которое можно перечислить. А затем придумать, как по любому конечному набору простых чисел указать еще одно простое число. Теперь, когда решение придумано, его можно изложить и без характерных для метода от противного слов: возьмем произвольный набор простых чисел, к ним можно добавить еще одно, затем еще одно и т. д. Так можно делать сколько угодно раз, поэтому простых чисел бесконечно много. Еще раз убеждаемся, что сила метода от противного не в магических заклинаниях: он и без них работает!

Задачи для самостоятельного решения

Задача 7.7. Петя сказал: «Если кот шипит, то рядом собака, и наоборот, если собаки рядом нет, то кот не шипит». Не сказал ли он что-то лишнее?

Задача 7.8. Все знают: когда Петя готов к уроку, он всегда поднимает руку. И вдруг…

1) Двоечник Вася точно знает, что сегодня Петя не готов к уроку. «Значит, он не будет поднимать руку», – думает Вася. Верно ли он рассуждает?

2) Марья Ивановна видит, что Петя не поднимает руку. «Ага, значит, он к уроку не готов. Вот сейчас вызову и двойку поставлю!» – думает коварная Марья Ивановна. Верно ли она рассуждает?

Задача 7.9. В вершинах куба расставлены числа 1, 2, 3, 4, 5, 6, 7, 8. Докажите, что есть ребро, числа на концах которого отличаются не менее чем на 3.

Задача 7.10. Десять друзей послали друг другу праздничные открытки, так что каждый послал пять открыток. Докажите, что найдутся двое, которые послали открытки друг другу.

Задача 7.11. Можно ли в кружочках расставить все цифры от 0 до 9 так, чтобы сумма трех чисел на каждом из шести отрезков была бы одной и той же?

Задача 7.12. Двое играют в игру «Щелк!». У них есть прямоугольная шоколадка, разделенная на дольки. Левая нижняя долька отравлена. Ходят по очереди. За ход можно съесть произвольную дольку и все находящиеся справа и сверху от нее. Съевший отравленную дольку проигрывает. Докажите, что у первого игрока есть выигрышная стратегия на любой прямоугольной шоколадке, в которой больше одной дольки (предъявлять стратегию не обязательно).

Задача 7.13. Круг разбит на 25 секторов, пронумерованных в произвольном порядке числами от 1 до 25. В одном из секторов сидит кузнечик. Он прыгает по кругу, каждым своим прыжком перемещаясь по часовой стрелке на количество секторов, равное номеру текущего сектора. Докажите, что в некотором секторе кузнечик не побывает никогда.

Задача 7.14. 1) Несколько мальчиков стали в ряд, при этом разница в росте между двумя соседними не более 10 см. Потом их построили по росту. Докажите, что и теперь разница в росте между двумя соседними мальчиками не более 10 см.

2) На уроке танцев 15 мальчиков и 15 девочек построили двумя параллельными колоннами, так что образовалось 15 пар. В каждой паре измерили разницу роста мальчика и девочки (разница берется по абсолютной величине, то есть из большего вычитают меньшее). Максимальная разность оказалась 10 см. В другой раз перед образованием пар каждую колонну предварительно построили по росту. Докажите, что максимальная разность будет не больше 10 см.

Задача 7.15. Найдите ошибку в рассуждении.

Докажем от противного, что ленивых учеников больше, чем прилежных. Предположим, что прилежных не меньше, чем ленивых. Несомненно, ленивых учеников больше, чем надо. Значит, получается, что прилежных учеников тем более больше, чем надо?! С этим мы, учителя, согласиться никак не можем. Получили противоречие, значит, исходное предположение было неверно, и на самом деле ленивых учеников больше, чем прилежных.