Быстрый поиск

Дипломная работа: Возвратные задачи

; .

Получили: ; ; ; ; .

Обобщая, приходим к выводу, что данная последовательность периодическая: если n = 5k+r (), тогда (для n ≥ 5)

Докажем методом математической индукции:

1) База: n=5 (верно, показано выше);

n=6 (верно, показано выше);

n=7 (верно, показано выше);

n=8 (верно, показано выше);

n=9 (верно, показано выше);

2) Индуктивный переход: пусть верно для всех чисел t ≤(n−1). Докажем для t=n: n = 5k + 0, тогда ;

· n = 5k + 1, тогда ;

· n = 5k + 2, тогда ;

· n = 5k + 3, тогда ;

· n = 5k + 4, тогда .

Из пунктов 1 и 2 следует: для n ≥ 5 .

Ответ: при всех n ≥ 0 и k, r Z+.

Задача 9. Иногда возможно использование «обратной индукции», т.е. доказательства от n к n−1, а не наоборот. К примеру, рассмотрим утверждение

P(n): ≤ , если x1,x2,…,xn ≥ 0

Оно справедливо для n=2, так как

(x1+x2)2 − 4x1x2 = (x1−x2)2 ≥ 0.

a) Полагая , докажите, что P(n) влечет P(n−1) при всяком n > 1.

b) Покажите, что P(n) и P(2) влекут P(2n).

c) Объясните, почему отсюда следует справедливость P(n) при всех n.

Решение. а) подставим в P(n):

P(n): ≤

преобразуем правую скобку: =

получили: ≤

разделим левую и правую части неравенства на (эта скобка не равна нулю, т.к. x1,x2,…,xn >0 и n > 1, т.к. случай всех хi=0 тривиальный, поэтому мы его не рассматриваем)

получим P(n−1): ≤ .

Следовательно, при P(n) влечет P(n−1) при всяком n>1.

b) запишем P(n) для двух конечных последовательностей чисел.

P(n): ≤ (для n первых членов)

≤ (для n членов начиная с )

перемножим эти два неравенства, используя свойство неравенств: если 0<a<b и 0<c<d, то ac<bd. Получим:

≤ .

Преобразуем правую скобку неравенства, используя утверждение Р(2)

P(2):

возведем левую и правую части неравенства в n-ую степень, получим

≤

Таким образом, получили:

P(2n): ≤ .

Следовательно, P(n) и P(2) влекут P(2n).

c) Выше было показано, что из P(n) следует P(n−1), а из P(n) и P(2) следует P(2n). Следовательно, мы можем утверждать, что P(n) выполняется для любого n > 1, т.к. P(от нечетного числа n) следует из P(от четного числа (n−1)), а P(от четного числа) следует из P(2) и P(от четного или нечетного числа) и т.д., в конечном итоге приходим к P(2), а оно выполняется.

Например, 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 – минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что

(1)

если n = 0

если n > 0

(2)

если n > 0

если n = 0

Решение.

Рассмотрим частные случаи: 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 > 0

если n = 0

Эксперимент с тремя дисками дает ключ и к общему правилу перемещения 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 на колышек А можно переместить за перекладываний. Получили соотношение:

если n > 0

если n = 0

И если мы вместо подставим (т.к. , показали выше), то получим нужную нам систему:

Таким образом, получили, что системы (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) можно переместить за перекладываний.

Получили рекуррентное соотношение:

при 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) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за перекладываний.