Возвратные задачи (стр. 5 из 9)
Задача 3.Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.
Решение. Занумеруем диски  |
Существует (в соответствии с условиями задачи) только три возможных расположения каждого диска на одном из колышков: либо на первом колышке (А), либо на втором колышке (B), либо на третьем колышке (С). Это будут перестановки длины nиз трех элементов. Например,
. 
Число перестановок длины kиз n элементов: 
. Следовательно, для нашего случая 
, т.е. 
– это все возможные различные расположения n дисков на трех колышках.В предыдущей задаче было показано, что наименьшее число перекладываний с колышка А на колышек Bчерез колышек С равно
−1. Таким образом, каждый раз перекладывая диск с одного колышка на другой, мы получаем все допустимые расположения n дисков на трех колышках (т.к. мы не перекладываем один диск с одного колышка на другой по несколько раз)Задача 4.Имеются ли какие-нибудь начальная и конечная конфигурации из n дисков на трех колышках, которые требуют более чем 
−1 перекладываний, чтобы получить одну из другой по исходным правилам Люка?
Решение. Докажем методом математической индукции, что любая начальная и конечная конфигурации из n дисков на трех колышках требуют не более чем
−1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.1) База: если n=1, то требуется одно перекладывание, тогда 1 ≤ 20−1 (верно);
2) Индуктивный переход: пусть для любой начальной и конечной конфигурации из n−1 дисков на трех колышках требуется не более чем
−1 перекладываний. Докажем для n дисков:· если начальная и конечная конфигурации не предполагают перекладывание самого большого нижнего диска, тогда мы перекладываем только n−1 верхних дисков, а по индуктивному предположению для этого потребуется не более чем
−1 перекладываний;· если начальная и конечная конфигурации предполагают перекладывание самого большого нижнего диска, тогда мы перекладываем n−1 верхних дисков, а по индуктивному предположению для этого будет достаточно
−1 перекладываний (т.е. n−1 верхних дисков разместили на одном колышке), затем перекладываем самый большой диск (одно перекладывание), и снова перекладываем n−1 верхних дисков, как требует конечная конфигурация (достаточно −1 перекладываний). Таким образом, получили, что потребуется не более чем −1 + 1+ −1= 
перекладываний.Из всего этого следует, что не существует начальной и конечной конфигурации из n дисков на трех колышках требующей более чем
−1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.Задача 5.Так называемая «диаграмма Венна» с тремя пересекающимися окружностями часто приводится для иллюстрации восьми возможных подмножеств, связанных с тремя заданными множествами:
Можно ли проиллюстрировать четырьмя пересекающимися окружностями шестнадцать возможностей, которые возникают в связи с четырьмя заданными множествами? 
Решение. Так как три пересекающиеся окружности иллюстрируют восемь различных подмножеств, то для того чтобы получить шестнадцать возможных подмножеств надо, чтобы четвертая окружность пересекала все восемь множеств. Но такого быть не может. Две произвольные окружности могут иметь не более двух точек пересечения, поэтому, проводя четвертую окружность, мы сможем получить максимум шесть дополнительных подмножеств. Так как возможно только два расположения четвертой окружности относительно трех данных окружностей: 1) четвертая окружность пересекает внешнее подмножество (рис. 1); 2) четвертая окружность лежит внутри трех пересекающихся окружностей (рис.2). 
рис.1 рис.2  |
Если добавленная окружность пересекает внешнее множество, то она не сможет пересечь как минимум два внутренних множества (зависит от радиуса окружности).
Если добавленная окружность лежит внутри трех пересекающихся окружностей, то она не пересекает внешнее множество и как минимум одно внутреннее множество.
Таким образом, получили, что четырьмя окружностями можно проиллюстрировать максимум 14 (8+6=14) возможных подмножеств.
Задача 6.Некоторые из областей, очерчиваемых n прямыми на плоскости, бесконечны, в то время как другие конечны. Какое максимально возможное число конечных областей?
Решение. Пусть
- максимальное число возможных конечных областей, очерчиваемых n прямыми. 
Рассмотрим частные случаи (при условии, что n-я прямая не параллельна никакой другой прямой (следовательно, она пересекает каждую из них), и не проходит ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах)):  | |||||||||
 | |||||||||
 |  | ||||||||
 | |||||||||
 | |||||||||
+ 1- максимальное число областей, на которые плоскость делится n прямыми).
(верно);
= 
=