Индукция

1. То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так: „Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует n лошадей (с номерами от 1 до n). По индуктивному предположению лошади с номерами от 1 до n — 1 одинаковой масти, и, аналогично, лошади с номерами от 2 до n имеют одинаковую масть. Но лошади посредине с номерами от 2 до n — 1 не могут изменять масть в зависимости от того, как они сгруппированы,—это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до n также должны быть одинаковой масти. Таким образом, все n лошадей одинаковой масти – что и требовалось доказать. Есть ли ошибка в приведенном рассуждении и какая именно?

2. Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек В, если прямой обмен дисками между А и В запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя класть на меньший.)

3. Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения встретятся все допустимые варианты размещения n дисков на трех колышках.

4. Так называемая „диаграмма Венна" с тремя пересекающимися окружностями часто приводится для иллюстрации восьми возможных подмножеств, связанных с тремя заданными множествами:

Можно ли проиллюстрировать четырьмя пересекающимися окружностями шестнадцать возможностей, которые возникают в связи с четырьмя заданными множествами?

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

6. Докажите по индукции равенство: .

7. На плоскости нарисованы несколько окружностей так, что с любой можно перейти на любую, не сходя с этих окружностей. Докажите по индукции, что тогда существует замкнутый путь, проходящий по всем участкам всех окружностей ровно по разу.

8. Докажите по индукции, что если в связном графе степени ровно двух вершин нечетны, то в нем есть эйлеров путь с концами в нечетных вершинах.

9. В стране 100 городов, некоторые из них соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (с пересадками). Докажите с помощью индукции, что можно побывать в каждом не более чем за 196 перелётов.

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

Поиск по сайту: