Ломаная линия подобна двум прямым с тем лишь отличием, что области сливаются, если «две» прямые не продолжать после их пересечения:
Области 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
Другой способ доказательства, когда k нечетно:
Можно заметить, что J(2n+1) − J(2n) = 2, тогда J(2m+k) = 2 + J(2m +
(k− −1))
J(2m+k) = 2 + 2(k −1) + 1 => J(2m+k) = 2k+1.
Из пунктов 1 и 2 следует: при m ≥ 0 и 0 ≤ k < 2m J(2m+k) = 2k+1.
Решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач. Поэтому изучим решение (8) и исследуем некоторые обобщения рекуррентного соотношения (7).
Обратимся к двоичным представлениям величин n и J(n) (т.к. степени 2 играли важную роль в нашем поиске решения).
n = (bm bm-1 b1 b0)2 ;
т.е. n = bm2m + bm-12m-1 + … + b12 + b0
где каждое bi равно 0 или 1, причем старший бит bm равен 1. Вспоминая, что n=2m+k, последовательно получаем:
n = (1 bm-1 … b1 b0)2
k = (0 bm-1 … b1 b0)2
(т.к. k= n−2m = 2m + bm-12m-1 + … + b12 + b0 − 2m = 0∙2m + bm-12m-1 + …+ b12 + b0)
2k = (bm-1 … b1 b0 0)2
(т.к. 2 k=2(bm-12m-1 +bm-22m-2 …+ b12 + b0)=bm-12m + bm-22m-1 + … + b122 + b02+0)
2k+1 = (bm-1 … b1 b0 1)2
J(n) = (bm-1 … b1 b0 bm)2
(т.к. J(n) = 2k+1 и bm = 1)
Таким образом, мы получили, что
J((bm bm-1 b1 b0)2) = (bm-1 … b1 b0 bm)2 (9)
т.е. J(n) получается путем циклического сдвига двоичного представления n влево на один сдвиг.
Рассмотрим свойства функции J(n).
Если мы начнем с n и итерируем J-функцию m+1 раз, то тем самым осуществляем циклический сдвиг на m+1 битов, а т.к. n является (m+1)-битовым числом, то мы могли бы рассчитывать в итоге снова получить n. Но это не совсем так. К примеру, если n = 27, то J(11011) = ((10111)2), но затем J(10111) = ((1111)2), и процесс обрывается: когда 0 становится старшим битом – он пропадает (т.к. принято, что коэффициент при старшей степени не равен 0). В действительности J(n) всегда должно быть ≤ n по определению, т.к. J(n) есть номер уцелевшего; и если J(n) < n, мы никогда не сможем получить снова n в следующих итерациях.
Многократное применение J порождает последовательность убывающих значений, достигающих, в конце концов «неподвижной точки» n, такой, что J(n)=n. Докажем, что J порождает последовательность убывающих значений, т.е. покажем, что 2n > 2n-1 + 2n-2 +…+21 + 1 при n ≥ 1.
Докажем методом математической индукции по n:
1) База: n=1, 21 > 20 (верно);
2) Индуктивный переход: пусть верно для всех чисел t ≤ (n–1) , т.е. выполняется неравенство 2t-1 > 2t-2 + 2t-3 +…+21 + 1. Докажем для t=n:
(2n-1 > 2n-2 + 2n-3 +…+21 + 1) умножим на 2, получим 2n > 2n-1 + 2n-2 +…+22 + 21. Левая и правая части неравенства четные числа, тогда между ними есть хотя бы одно нечетное число, следовательно, прибавление 1 к правой части неравенства (четное число +1 = нечетное число) неравенство не изменит. Т.о. получаем нужное нам неравенство: 2n > 2n-1 + 2n-2 +…+21 + 1 при n ≥ 1.
Свойство циклического сдвига позволяет выяснить, чем будет «неподвижная
точка»: итерирование функции m и
более раз всегда будет порождать набор из одних единиц со значением 
, где ν(n) – число равных 1 битов в двоичном представлении n (это следует из того, что имеем
последовательность 20 , 21 , 22 ,…,2n-1, 2n, и по формуле суммы геометрической прогрессии
получаем 
). Так, например: ν(27) = ν(11011)
= 4, тогда J(J(…J(27)…)) =24 −1=15
|
Теперь давайте вернемся к
нашему первоначальному предположению, что J(n) = 
при четном n. Вообще-то это неверно, но мы выясним, когда это верно: J(n) = 
, тогда 2k+1 = 
=> k = 
. Если
число k = =
целое,
то n= 2m + k будет решением,
т.к. k < 2m. Нетрудно убедиться, что (2m − 2) кратно 3, когда m нечетно, но не когда m четно. Действительно, если m – нечетно, то 2m − 2 = 22k+1 − 2 = 2(4k − 1). Докажем методом
математической индукции, что (4k − 1) делится на три (где 
):
1) База: k=1, 4−1=3, три делится на три (верно);
2) Индуктивный переход: пусть верно для всех чисел t ≤(k−1), т.е (4t−1) делится на три. Докажем для t=k:
4k − 1 = 4(4k-1 − 1) + 3 
(4k-1 − 1) делится на три, и 3
делится на три => (4к−1) делится на три.
Таким образом, показали, что для m – нечетного (2m − 2) делится на 3.
Теперь покажем, что при m – четном (2m − 2) не делится на 3. Предположим
противное: пусть (2m −
2) делится на 3 при четном m,
тогда 
, числа 2 и 3 взаимнопростые, следовательно, (
) должно делится на 3, т.е. 
=3q 
, но 
, a 
, т.е. получили, что 
, а это не верно. Следовательно, наше
предположение не верно и 2m −
2 не делится на 3 при четном m.
