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

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 (3)

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

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 ?????? ???????? ????????

2

??????? ??????:

Z1 = 2	Z2 = 7

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

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

Z_n = L_{2 n} − 2n = = 2n² −n+1 при n ≥ 0 (4)

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

L_n ~ ,

Z_n ~ 2n² ,

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

1.3. Задача Иосифа Флавия

Формулировка задачи: в круг выстроено n человек, пронумерованных числами от 1 до n, и исключается каждый второй из оставшихся до тех пор, пока не уцелеет только один человек. Определить номер уцелевшего, J(n).

Например, при n = 10 порядок исключения – 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5, т.е. J(10) = 5. При n = 2 номер уцелевшего J(2) = 1. Можно было бы предположить, что J(n) = при четном n. Однако это не так – предположение нарушается при n = 4 и n = 6.

N	1	2	3	4	5	6
J(n)	1	1	3	1	3	5

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

Итак, решим поставленную задачу.

Допустим, что первоначально имеется 2n людей. После первого обхода мы остаемся с номерами:

Следующий обход будет начинаться с номера 3. Это тоже самое, если бы мы начинали с n людей, за исключением того, что номер каждого уцелевшего удваивается и уменьшается на 1. Тем самым

J(2n) = 2∙J(n) − 1 при n ≥ 1 (5)

Теперь можно быстро продвигаться к большим n. Например, нам известно, что J(10) = 5, поэтому J(20) = 2∙J(10) − 1 = 2∙5 − 1 = 9, аналогично J(40) = 2∙J(20) − 1 = 17, и вообще можно вывести, что

J(5∙2^m ) = 2^{m +1} +1.

J(5∙2^m ) = J(2∙2^{m -1} ∙5) = 2∙J(2^{m -1} ∙5) − 1 = 2∙J(2∙2^{m -2} ∙5) − 1 = 2² ∙J(2^{m -2} ∙5)− 2¹ − 1 = =2³ ∙J(2^{m -3} ∙5) − 2² − 2¹ − 1=2⁴ ∙J(2^{m -4} ∙5) − 2³ − 2² − 2¹ − 1= …= 2^m ∙J(5) − (2^{m -1} +2^{m -2} ++…+2³ +2² +2¹ +1) = 2^m ∙J(5) − = 2^m ∙3 − 2^m + 1 = 2^{m +1} +1.

Теперь посмотрим, что будет в случае, когда имеется 2n+1 людей. После первого обхода жертва с номером 1 уничтожается сразу после жертвы с номером 2n, и мы остаемся с номерами:

Получили почти первоначальную ситуацию с nлюдьми, но на этот раз номера уцелевших удваиваются и увеличиваются на 1. Таким образом,