Занимательные задачи: метод от противного. Часть 1
Предмет: Математика, 5 класс
Автор: Черняев Игорь Владимирович

Цели и задачи урока: сформировать представление о методе доказательства от противного как о приемлемом и полноценном методе доказательства высказываний.

Предметные результаты: истинность доказываемого тезиса устанавливается посредством опровержения противоречащего ему суждению.

Метапредметные и личностные результаты: развивать вычислительные навыки, умения решать задачи, развивать логическое мышление учащихся, воспитывать интерес к математике.

Здравствуйте. Какие ассоциации возникают у вас когда вы слышите словосочетание «метод от противного»? Наверное, многие могут подумать, что это такой метод воспитания, когда вы решаете очень противные задачи и в итоге заниматься этим предметом вам становится противно. Ну или когда вы так противно рассказываете решение, что челны жюри олимпиады предпочитают засчитать вам задачу, лишь бы больше этого не слышать… На самом деле, обычно, под данным названием понимают немного другой метод решения задач.

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

Задача 1. За круглым столом сидят 7 пациентов психической лечебницы. Некоторые из них всегда говорят правду, другие всегда лгут. Каждый сидящий за столом сказал: "У моих соседей разные виды помешательства". Докажите, что все они патологические лжецы. Пусть это не правда. Пусть среди них есть паталогический правдолюб. Тогда по разную сторону от него люди с разными видами помешательства. С соседом правдолюбом та же история. И так далее. Получаем:

Л1-Пр2-Пр3-Л4-Пр5-Пр6-Л7-Пр1. То есть Л=Пр. Что странно…

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

кто смог поставить пять своих значков подряд по вертикали, горизонтали или диагонали. Докажите, что крестики могут как минимум не проиграть.

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

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

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

Комментарий.

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

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

Предположим противное:

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

Комментарий.

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

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

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

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

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

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

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

Метод от противного оказался эффективен, потому что помог от бесконечного количества, с которым непонятночто делать, перейти к конечному, которое можно перечислить.

Подведем итог:

мы достаточно свободно научились применять метод от противного при решении задач.

Дополнительная информация

Рекомендуемые практикумы:

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

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

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

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

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

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