Инесса Раскина - Логика для всех. От пиратов до мудрецов

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

Задача 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), неизвестно до сих пор. Как не найдено и никакой формулы, позволяющей бесконечно вычислять одно простое число за другим. А некоторые простые по формулировке вопросы теории чисел решены весьма сложными современными методами (например, великая теорема Ферма или тернарная проблема Гольдбаха). Но вот вопрос о бесконечности множества простых чисел древние греки смогли не только поставить, но и решить. Приведем удивительное по красоте и простоте доказательство от противного, восходящее к «Началам» Евклида.

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