Смекни!
smekni.com
Математика

Возвратные задачи (стр. 2 из 9)

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

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

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

Т0+1 = 1,

Тn+1 = 2Tn-1+2 при n>0.

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

U0 = 1

Un= 2Un-1 при n>0.

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

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

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

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

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

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

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

Ln≤ Ln-1+ n при n>0

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

L0 = 1

Ln= Ln-1+ n при n> 0

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

Ln= Ln-1+ n = Ln-2+ (n−1) + n = Ln-3+ (n−2) + (n−1) + n = … = L0+ 1 + 2+ +… + (n−2) + (n−1) + n = 1 +

Ln =

+ 1 при n ≥ 0 (3)

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

1) База: n=0, L0=

= 1 (верно);

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

Ln= Ln-1+ n

=
=

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

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

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

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

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

Zn = L2n− 2n =

= 2n2 −n+1 при n ≥ 0 (4)

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

Ln ~

,

Zn ~ 2n2 ,

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

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∙2m) = 2m+1+1.

J(5∙2m) = J(2∙2m-1∙5) = 2∙J(2m-1∙5) − 1 = 2∙J(2∙2m-2∙5) − 1 = 22∙J(2m-2∙5)− 21 − 1 = =23∙J(2m-3∙5) − 22 − 21 − 1=24∙J(2m-4∙5) − 23 − 22 − 21 − 1= …= 2m∙J(5) − (2m-1+2m-2++…+23+22+21+1) = 2m∙J(5) −

= 2m∙3 − 2m+ 1 = 2m+1+1.

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

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

J(2n+1) = 2∙J(n) + 1 при n ≥ 1 (6)

Объединение уравнений (5) и (6) с уравнением J(1)=1 дает рекуррентное соотношение, которое определяет J во всех случаях:

J(1) = 1

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

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

Решим данное рекуррентное соотношение. Составим таблицу первых значений J(n):

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Если сгруппировать значения n по степеням двойки (в таблице эти группы отделены вертикальными линиями), то в каждой группе J(n) всегда будет начинаться с 1, а затем увеличиваться на 2. Итак, если записать n в виде n = 2m+k, где 2m – наибольшая степень 2, не превосходящая n, а k – то, что остается, то решение рекуррентного соотношения должно иметь вид:

J(2m+k) = 2k+1 при m≥ 0 и 0 ≤ k< 2m (8)

(Если 2m≤ n< 2m+1, то остаток k= n−2mудовлетворяет неравенству 2m≤k+2m<2m+1, т.е. 0 ≤ k < 2m)

Докажем (8) методом математической индукции по m.

1) База: m = 0 => k = 0

J(20+0) = J(1) = 2∙0 + 1 = 1 (верно);

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

a) если m> 0 и 2m+k=2n, то k – четно и J(2m+k) = J(2(2m-1+

)) =
2∙J(2m-1+
) − 1
2(2∙
+ 1) −1 = 2k + 1

b) если m > 0 и 2m+k=2n+1, то k – нечетно (т.е. k=2t+1) и J(2m+k) = = J(2m+(2t+1)) = J(2(2m-1+t) +1)

2∙J(2m-1+ t) + 1
2(2t+1) + 1 = 2k + 1
 
назад
читать дальше
1
2
3
4
5
6
7
8
9
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.