Задача о ханойской башне

1. Задача о ханойской башне

Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск, и не помещая больший диск на меньший.

Будем решать эту задачу в общем виде, т.е. посмотрим, что будет в случае n дисков.

Будем говорить, что T_n есть минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка.

Рассмотрим крайние случаи: Т₀ = 0, T₁ = 1, T₂ = 3, T₃ = 7. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n − 1) меньших дисков на любой из колышков (что требует Т_{n- 1} перекладываний), затем перекладываем самый большой диск (одно перекладывание ) и, наконец, помещаем (n − 1) меньших дисков обратно на самый большой диск (еще Т_{n- 1} перекладываний). Таким образом, n дисков (при n > 0) можно переместить самое большое за 2T_{n – 1} + 1 перекладываний (т.е. достаточно перекладываний):

T_n≤ 2T_{n – 1} + 1.

Сейчас покажем, что необходимо 2T_{n – 1} + 1 перекладываний. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем, (n − 1) меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере Т_{n- 1} перекладываний. Самый большой диск можно перекладывать и более одного раза.

Но после перемещения самого большого диска в последний раз мы обязаны поместить (n − 1) меньших дисков (которые опять должны находиться на одном колышке) обратно на наибольший диск, что также требует Т_{n- 1} перекладываний.

Следовательно,

T_n≥ 2T_{n – 1} + 1.

Эти два неравенства вместе с тривиальным решением при n = 0 дают рекуррентное соотношение:

 

Т₀ = 0

T_n= 2T_{n – 1} + 1 при n > 0 (41)

При достаточно большом n для вычисления Т_n потребуется слишком много времени, поэтому получим Т_nв простой, компактной, «замкнутой форме», что позволит вычислить Т_n быстро.

Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим:

Т₃ = 2∙3 + 1 = 7; Т₄ = 2∙7 + 1; Т₅ = 2∙15 + 1; Т₆ = 2∙31 + 1 = 63.

Теперь можно сделать предположение, что

Т_n=2ⁿ − 1 при n ≥ 0. (42)

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

1)               База: n = 0, Т₀=2⁰ – 1 = 1 – 1 = 0 (верно);

2)               Индуктивный переход: пусть доказано для всех чисел t ≤ (n – 1). Докажем для

 t = n: Т_n= 2T_{n – 1} +1  2(2^{n – 1} − 1) + 1 = 2∙2^{n – 1} − 2 + 1 = 2ⁿ − 1

Из пунктов 1 и 2 следует: при n ≥ 0 Т_n= 2ⁿ − 1

Второй способ решения.

К обеим частям соотношения (41) прибавим 1:

 

Т₀+1 = 1,

Т_n+1 = 2T_{n – 1} + 2 при n > 0.

Обозначим U_n= T_n+ 1, тогда получим

 

U₀ = 1

U_n= 2U_{n- 1} при n > 0.

Решением этой рекурсии есть U_n= 2ⁿ; следовательно Т_n = 2ⁿ−1.

2. Задача о разрезании пиццы

Формулировка задачи: сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или, каково максимальное число L_n областей, на которые плоскость делится n прямыми?

1

Снова начнем с рассмотрения крайних случаев.

Эксперимент с тремя прямыми показывает, что добавленная третья прямая может рассекать самое большое три старых области вне зависимости от того, как расположены первые две прямые:

Таким образом, L₃ = 4 + 3 = 7 – самое большое, что можно сделать.

Обобщая, приходим к следующему выводу: новая n-я прямая (при n > 0) увеличивает число областей на k ó когда рассекает k старых областей ó когда пересекает прежние прямые в (k − 1) различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать (n − 1) старых прямых не более чем в (n − 1) различных точках, и мы должны иметь k ≤ n. Установлена верхняя граница:

L_n≤ L_{n – 1} + n при n > 0

В этой формуле можно достичь равенства следующим образом: проводим n-ю прямую так, чтобы она не была параллельна никакой другой прямой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому рекуррентное соотношение имеет вид:

 

L₀ = 1

L_n= L_{n- 1}+ n при n > 0

Теперь получим решение в замкнутой форме.

L_n= L_{n – 1} + n = L_{n – 2} + (n−1) + n = L_{n- 3}+ (n−2) + (n−1) + n = … = L₀+ 1 + 2+ +… + (n−2) + (n−1) + n = 1 +

L_n =  + 1 при n ≥ 0 (43)

Докажем полученное равенство методом математической индукции.

1)                База: n=0, L₀= = 1 (верно);

2)                Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n:

L_n= L_n-1+ n   =  =

Из пунктов 1 и 2 следует: при n ≥ 0

L_n =  + 1

3

А теперь небольшая вариация на тему прямых на плоскости: предположим, что вместо прямых линий мы используем ломаные линии, каждая из которых представлена одним «зигом». Каково максимальное число Z_n областей, на которые плоскость делится n такими ломаными линиями?

Частные случаи:

		Z1 = 2				Z2 = 7

 

Ломаная линия подобна двум прямым с тем лишь отличием, что области сливаются, если «две» прямые не продолжать после их пересечения:

Области 2, 3 и 4, которые были бы разделены при наличии двух прямых, превращаются в единую область в случае одной ломаной линии, т.е. мы теряем две области. И если привести все в надлежащий порядок, то точка излома должна лежать «по ту сторону» пересечений с другими линиями, и мы теряем только две области на одну линию. Таким образом,

Z_n = L_2n− 2n =  = 2n² −n+1 при n ≥ 0 (44)

Сравнивая решения в замкнутой форме (43) и (44), мы приходим к выводу, что при большом n,

L_n ~ ,

Z_n ~ 2n² ,

так что ломаные линии дают примерно в четыре раза больше областей, чем прямые.

Глава 2 (практическая часть)

1. Рассмотрим последовательность квадратов натуральных чисел:

u₁ = 1², u₂ = 2², u₃ = 3², . . . , u_n= n², . . . (*)

Здесь u_{n + 1} = (n + 1)² = n² + 2n + 1 и, следовательно,

u_{n + 1} = u_n+ 2n + 1. (1)

Увеличивая n на единицу, получим:

u_{n + 2} = (n + 2)² = n² + 4n + 4 = (n² + 2n + 1) + 2n + 3 = u_{n + 1}+ 2n + 3.

u_{n + 2} = u_{n + 1}+ 2n + 3 . (2)

Вычитая почленно (1) из (2), получим:

u_{n + 2} - u_{n + 1}= (u_{n + 1}+ 2n + 3) – (u_{n + 1} = u_n+ 2n + 1 ) = u_{n + 1}- u_n + 2,

u_{n + 2} = 2u_{n + 1}- u_n + 2. (3)

Увеличивая в равенстве (3) n на единицу, будем иметь:

u_{n + 3} = (n + 3)² = n² + 6n + 9 = (n² + 4n + 4) + 2n + 5 = u_{n + 2}+ 2n + 5,

u_{n + 3} = u_{n + 2}+ 2n + 5. (4)

Вычитая почленно (2) из (4), получим:

u_{n + 3} - u_{n + 2} = (u_{n + 2}+ 2n + 5) – (u_{n + 1}+ 2n + 3 ) = u_{n + 2}- u_{n + 1} + 2,

u_{n + 3} = 2u_{n + 2}- u_{n + 1} + 2, (5)

Вычитая почленно (3) из (5), получим:

u_{n + 3} - u_{n + 2}= (2u_{n + 2}- u_{n + 1} + 2) – (2u_{n + 1}- u_n + 2) = 2u_{n + 2}- 3u_{n + 1} + u_n ,

или u_{n + 3} = 3u_{n + 2}- 3u_{n + 1} + u_n.. (6)

Получили возвратное уравнение третьего порядка, т. е. k = 3, a₁ = 3, a₂ = -3, a₃ = 1.

Следовательно, последовательность (*) есть возвратная последовательность третьего порядка.

2. Рассмотрим последовательность кубов натуральных чисел:

u₁ = 1³, u₂ = 2³, u₃ = 3³, . . . , u_n= n³, . . . (**)

Здесь u_{n + 1} = (n + 1)³ = n³ + 3n² + 3n + 1 и, следовательно,

u_{n + 1} = u_n+ 3n² + 3n + 1. (7)

Увеличивая n на единицу, получим:

u_{n + 2} = (n + 2)³ = n³ + 6n² + 12n + 8 = (n³ + 3n² + 3n + 1) + 3n² + 9n + 7 = = u_{n + 1}+ 3n² + 9n + 7,

u_{n + 2} = u_{n + 1}+ 3n² + 9n + 7. (8)

Вычитая почленно (7) из (8), получим:

u_{n + 2} - u_{n + 1}= (u_{n + 1}+ 3n² + 9n + 7) – (u_n+ 3n² + 3n + 1) = u_{n + 1}- u_n + 6n + 6,

u_{n + 2} = 2u_{n + 1}- u_n + 6n + 6. (9)

Увеличивая в равенстве (9) n на единицу, будем иметь:

u_{n + 3} = (n + 3)³ = n³ + 9n² + 27n + 27 = (n³ + 6n² + 12n + 8) + 3n² + 15n + 19= u_{n + 2}+ 3n² + 15n + 19,

u_{n + 3} = u_{n + 2}+ 3n² + 15n + 19. (10)

Вычитая почленно (8) из (10), получим:

u_{n + 3} - u_{n + 2} = (u_{n + 2}+ 3n² + 15n + 19) – (u_{n + 1}+ 3n² + 9n + 7) = u_{n + 2}- u_{n + 1} + 6n + 12,

u_{n + 3} = 2u_{n + 2}- u_{n + 1} + 6n + 12. (11)

Вычитая почленно (9) из (11), получим:

u_{n + 3} - u_{n + 2}= (2u_{n + 2}- u_{n + 1} + 6n + 12) – (2u_{n + 1}- u_n + 6n + 6) = 2u_{n + 2}- 3u_{n + 1} + u_n + 6,

или u_{n + 3} = 3u_{n + 2}- 3u_{n + 1} + u_n + 6_. (12)

Увеличивая в равенстве (12) n на единицу, будем иметь:

u_{n + 4} = (n + 4)³ = n³ + 12n² + 48n + 64 = (n³ + 9n² + 27n + 27) + 3n² + 21n + + 37 = u_{n + 3}+ 3n² + 21n + 37,

u_{n + 4} = u_{n + 3}+ 3n² + 21n + 37. (13)

Вычитая почленно (10) из (13), получим:

u_{n + 4} - u_{n + 3} = (u_{n + 3}+ 3n² + 21n + 37) – (u_{n + 2}+ 3n² + 15n + 19) = = u_{n + 3}- u_{n + 2} + 6n + 18,

u_{n + 4} = 2u_{n + 3}- u_{n + 2} + 6n + 18. (14)

Вычитая почленно (11) из (14), получим:

u_{n + 4} - u_{n + 3}= (2u_{n + 3}- u_{n + 2} + 6n + 18) – (2u_{n + 2}- u_{n + 1} + 6n + 12) = = 2u_{n + 3}- 3u_{n + 2} + u_{n + 1} + 6,

или u_{n + 4} = 3u_{n + 3}- 3u_{n + 2} + u_{n + 1} + 6_. (15)

Вычитая почленно (12) из (15), получим:

u_{n + 4} - u_{n + 3}= (3u_{n + 3}- 3u_{n + 2} + u_{n + 1} + 6) – (3u_{n + 2}- 3u_{n + 1} + u_n + 6) = 3u_{n + 3}- 6u_{n + 2} + 4u_{n + 1} - u_n ,

или u_{n + 4} = 4u_{n + 3}- 6u_{n + 2} + 4u_{n + 1} - u_{n .} (15)

Получили возвратное уравнение четвёртого порядка, т. е. k = 4, a₁ = 4, a₂ = -6, a₃ = 4, a₄ = - 1.

Следовательно, последовательность (**) есть возвратная последовательность четвёртого порядка.

3. Проверим, что условие теоремы:

Для того чтобы система k линейных алгебраических уравнений

Аx₁ + Вy₁ + . . . + Cz₁ = u₁

Аx₂ + Вy₂ + . . . + Cz₂ = u₂

. . . . . . . . . . . . . . . . . . . . .  (16)

Аx_k+ Вy_k+ . . . + Cz_k= u_k

с k неизвестными имела решение A, B, . . . , C и притом единственное, при любых значениях правых частей u₁, u₂, u₃, . . . , u_k, необходимо и достаточно, чтобы соответствующая ей однородная система

Аx₁ + Вy₁ + . . . + Cz₁ = 0

Аx₂ + Вy₂ + . . . + Cz₂ = 0

. . . . . . . . . . . . . . . . . . . . .  (17)

Аx_k+ Вy_k+ . . . + Cz_k= 0

имела бы одно только нулевое решение: A = B = . . . = C = 0 – выполняется в частных случаях

x₁ = 0,y₁ = 0, . . . , z₁ = 0

x₂ = 0,y₂ = 0, . . . , z₂ = 0 (18)

x_k = 0, y_k = 0, . . . , z_k = 1

x₁ = 1,y₁ = 1, . . . , z₁ = 1

x₂ = 0,y₂ = 1, . . . , z₂ = 1 (19)

x_k = 0, y_k = 0, . . . , z_k = 1

1) x₁ = 0,y₁ = 0, . . . , z₁ = 0

x₂ = 0,y₂ = 0, . . . , z₂ = 0

x_k= 0, y_k= 0, . . . , z_k= 1

Тогда однородная для (16) система (17) примет вид

 

А•1 = 0

В•1= 0

. . . . . .

C•1= 0

А = 0

В= 0

. . . . . .

C= 0

Т. е. A = B = . . . = C = 0.

Получили, что k линейных алгебраических уравнений (16) с k неизвестными имеет единственное решение

A = B = . . . = C = 0.

2) x₁ = 1,y₁ = 1, . . . , z₁ = 1

x₂ = 0,y₂ = 1, . . . , z₂ = 1

x_k = 0, y_k = 0, . . . , z_k = 1

Тогда однородная для (16) система (17) примет вид

А•1+ В•1+ . . . + C•1 = 0

В•1+ . . . + C•1 = 0

. . . . . . . . . . . . . . . . . . . . .

C•1= 0

Решая эту систему с конца, получим A = B = . . . = C = 0. Получили, что k линейных алгебраических уравнений (16) с k неизвестными имеет единственное решение A = B = . . . = C = 0.

Заключение

В данной работе поставленные цели достигнуты.

В работе изучены основные теоретические сведения о возвратных последовательностях, приведены примеры таких последовательностей, также доказаны некоторые теоремы. Нужно заметить, что часть теоретического материала рассматривается именно через примеры, с помощью которых выводятся основные формулы теории возвратных последовательностей. Также затронута тема «возвратные задачи», в работе подробно разобраны некоторые из них. Третья глава посвящена изучению и применению возвратных последовательностей в школьном курсе математики, что можно включить в учебную программу факультатива по математике в средней школе.

В практической части применены полученные знания теории возвратных последовательностей. А именно: доказано по определению, что последовательности являются возвратными и проверено условие выполнения теоремы в частных случаях.

Тема «Возвратные последовательности» не является изолированной, Она близка к школьному курсу математики (арифметическая и геометрическая прогрессии, последовательности квадратов и кубов натуральных чисел и т.д.), используется в высшей алгебре, геометрии, математическом анализе и других математических дисциплинах. Теория возвратных последовательностей составляет особую главу математической дисциплины, называемой исчислением конечных разностей; представляет собой частную главу о последовательностях.

Таким образом, в данной курсовой работе изучена очень важная и актуальная на сегодняшний день тема.

Список литературы

1.     Грехем, Р. Конкретная математика. Основание информатики. / Р. Грехем, Д. Кнут, О. Паташник. Пер. с англ. – М.:Мир, 1998. – С. 17−37.

2.     Маркушевич А. И. Возвратные последовательности. Популярные лекции по математике. - М.: Наука, 1950.

3.     Мантуров О. В. Математика в понятиях, определениях и терминах. Ч.2 / О. В. Мантуров, Ю. К. Солнцев, Ю. И. Соркин, Н. Г. Федин; Под. ред. Л. В. Сабинина. – М.: Просвещение, 1982. – С. 207–208.