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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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