Занятие 7. Доказательство от противного
Задача 1. Если рыцарь встречает дракона, то рыцарь вступает в
бой.
1) Составьте к этому высказыванию обратное, противоположное и
противоположное обратному.
2) Известно, что рыцарь вступил в бой. Означает ли это, что он
встретил дракона?
3) Рыцарь не вступил в бой. Означает ли это, что он не встретил
дракона?
Задача 2. Многозначное число не содержит повторяющихся цифр.
Докажите, что оно не может быть произведением двух меньших чисел,
состоящих только из единиц и нулей.
Задача 3. Двое играют в «крестики-нолики» на бесконечной доске.
Крестики ходят первыми. Выигрывает тот, кто смог поставить пять
своих значков подряд по вертикали, горизонтали или диагонали. До-
кажите, что крестики могут как минимум не проиграть.
Задача 4. В клетках шахматной доски как-то расставлены все на-
туральные числа от 1 до 64. Докажите, что найдутся две соседние по
стороне или по вершине клетки, числа в которых отличаются не мень-
ше чем на 9.
Задача 5. Острова архипелага связаны мостами так, что с каждого
острова можно дойти до любого другого. Не более чем с двух островов
ведет нечетное число мостов, а с остальных — четное. «Докажем», что
можно обойти архипелаг, пройдя по каждому мосту ровно один раз.
«Доказательство». Предположим противное: хотя бы с трех остро-
вов ведет нечетное число мостов. Заходя на остров, мы «тратим» два
моста: по одному вошли, по другому вышли. Поэтому мосты, выхо-
дящие с каждого острова, можно объединить в пары. Нечетное число
мостов может быть только на самом первом острове (мы с него вышли
первый раз, не заходя перед этим) и на последнем (зашли, но не вы-
шли). Если островов с нечетным числом мостов хотя бы три, приходим
к противоречию, и пройти по всем мостам ровно один раз нельзя. А ес-
ли таких островов не более двух, то можно.
Верно ли это «доказательство»?
Достарыңызбен бөлісу: 
