Из пунктов 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 прямыми?
Z2 = 7 |
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 + 1b) если 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