Возвратные задачи (стр. 7 из 9)
Например, P(9) следует из P(8), а P(8) следует из P(2) и P(4), P(4) следует из P(2) и P(2), а P(2) выполняется.
Задача 10.Пусть Qn - минимальное число перекладываний, необходимых для перемещения башни из n дисков с колышка А на колышек B, если все перекладывания осуществляются по часовой стрелке – т.е. с А на B, или с B на другой колышек, и с другого колышка на А. Кроме того, пусть Rn– минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что
Решение. Рассмотрим частные случаи: Q0=0, R0=0; Q1=1, R1=2; Q2=5, R2=7; Q3=15= =R2+1+R2, R3=21= Q3+1+Q2.
Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков cколышка А на колышек B по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка А на C, через колышек B(для этого потребуется
перекладываний, т.к. это тоже самое если бы мы перекладывали диски с колышка Bна колышек А через колышек С), затем перекладываем самый большой диск cколышка A на колышек B (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка C на B(что требует перекладываний, по тем же соображениям). Таким образом, n дисков (при n>0) cколышка A на колышек B можно переместить за 
перекладываний. Получили соотношение: Эксперимент с тремя дисками дает ключ и к общему правилу перемещения n дисков cколышка Bна колышек A по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка B на А (что требует Rn-1 перекладываний), затем перекладываем самый большой диск cколышка B на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка А на B(что требует Qn-1 перекладываний), затем перекладываем самый большой диск c колышек С на колышек А (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков с колышка B на колышек А (еще Rn-1 перекладываний). Таким образом, n дисков (при n>0) cколышка B на колышек А можно переместить за
перекладываний. Получили соотношение: 
И если мы вместо 
подставим 
(т.к. , показали выше), то получим нужную нам систему: Таким образом, получили, что системы (1) и (2) справедливы.
Задача 11.Двойная ханойская башня состоит из 2nдисков nразличных размеров – по два диска каждого размера. Как и в случае обычной башни, за один раз разрешается перекладывать только один диск и нельзя класть больший диск на меньший.
a) Сколько перекладываний необходимо для перемещения двойной башни с одного колышка на другой, если диски одинаковых размеров неотличимы друг от друга?
b) Что если в окончательном расположении дисков требуется воспроизвести исходный порядок всех одинаковых дисков сверху донизу?
Решение. a) Пусть
- минимальное число перекладываний башни 2n дисков с одного колышка на другой. Рассмотрим частные случаи: P0=0, P2=2, P4=6, P6=14. Эксперимент с шестью дисками дает ключ к общему правилу перемещения 2n дисков: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует 
перекладываний), затем перекладываем 2 самых больших диска (одно перекладывание), потом помещаем (2n−2) меньших дисков на большие диски (что требует перекладываний). Таким образом, 2n дисков (при n>0) можно переместить за 
перекладываний.Получили рекуррентное соотношение:
Решим данное соотношение. P0 =0=
, P2 =2=
, P4 =6 = 
, P6== 14=
(Здесь Tn = 2n−1 - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка) 
гипотеза: 
при n≥ 0Докажем методом математической индукции по числу n, что
при n≥ 0.1) База: n=1
(верно);2) Индуктивный переход: пусть верно для всех чисел t≤(2n−2). Докажем для 2n дисков:
Из пунктов 1 и 2 следует, что
при n ≥ 0.b) Пусть
- минимальное число перекладываний башни из 2n дисков с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу.Рассмотрим частные случаи: R0=0, R2=3, R4=11. Эксперимент с четырьмя дисками дает ключ к общему правилу перемещения 2n дисков в исходном порядке: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует
перекладываний), затем перекладываем два самых больших диска на свободный колышек (два перекладывания; эти диски будут положены неправильно), потом перекладываем (2n−2) меньших дисков на свободный колышек (что требует перекладываний), затем снова перекладываем два самых больших диска (два перекладывания; эти диски будут положены правильно), и, наконец, перекладываем (2n−2) меньших дисков на большие диски в исходном порядке (потребуется 
перекладываний). Таким образом, 2n дисков (при n>0) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за 
перекладываний.Получили рекуррентное соотношение:
(*)Решим данное соотношение. R2 = 3 = 2P2−1, R4 = 11 = 2P4−1, R6 = 27 = 2P6−1
гипотеза: 
при n > 0.Докажем методом математической индукции по числу n, что
при n> 0.1) База: n=1
(верно);2) Индуктивный переход: пусть верно для всех чисел t≤(2n−2). Докажем для 2n дисков:
Из пунктов 1 и 2 следует, что
при n> 0.