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

2

1

3

4

L2=4

1

L0=1

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

1а

1b

2

4a

4b

3a

3b

Таким образом, 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                                       (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

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

2

1

1

4

6

5

7

		Z1 = 2				Z2 = 7

 

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

1

4

3

2

Области 2, 3 и 4, которые были бы разделены  при наличии двух прямых, превращаются в единую область в случае одной  ломаной линии, т.е. мы теряем две  области. И если привести все в  надлежащий порядок, то точка излома должна лежать «по ту сторону» пересечений  с другими линиями, и мы теряем только две области на одну линию. Таким образом,  
                     Z_n = L_2n − 2n =  = 2n² −n+1          при n ≥ 0                      (4)  
Сравнивая решения в замкнутой форме (3) и (4), мы приходим к выводу, что при большом n,  
                                    L_n ~ ,  
                                       Z_n ~ 2n² ,  
так что ломаные линии дают примерно в четыре раза больше областей, чем прямые.