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

Оглавление

1. Задача Иосифа Флавия.
2. Задача о ханойской башне.
3. Задача о разрезании пиццы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом.

Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам.

В современной формулировке задачи участвует n воинов, стоящих по кругу, и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который останется последним.

Рекуррентные соотношения

Если известно решение  задачи для некоторого числа воинов, то его можно использовать для  решения задачи с на единицу большим числом воинов. Для имеем

.

Для имеем

.

Очевидно для общего случая будем иметь

.

Возможно построение рекурсивных соотношений, которые  сходятся намного быстрее чем линейные. Вот пример решения задачи для с логарифмическим числом шагов рекурсии:

.

Замкнутая формула

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

Способы решения

Переборное решение

Рассмотрим ещё  два способа решения задачи, не опирающихся на приведенную выше формулу. Несмотря на то, что они  сложнее для вычисления в плане  вычислительной скорости, все же, алгоритм более нагляден. Давайте повторим в ОЗУ события, происходившие  в легенде.

Способ первый

Будем хранить в  массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей  были записаны в элементах массива  с 0 по N — 1 (это свойство будет использоваться для операции взятия остатка). Когда  воин будет умирать, будем удалять  его из массива, и тех, кто стоял  за ним, «сдвигать» на один элемент  влево.

Заметим, что если мы уже убили L человек, то в живых  осталось M = N — L. Пусть мы только что (на L-ом шаге) убили человека, который был записан в нашем массиве в элементе с номером j (и сдвинули людей, которые были записаны в массиве в элементах с j + 1 по M на один элемент влево). Тогда следующим нужно убивать человека, который записан в этом массиве в элементе с номером (j + k — 1) % M.

Способ второй

Заведем массив, где  будем помечать мертвых воинов (то есть в i-м элементе хранится, жив воин i, или уже нет). Пусть у нас на текущем шаге M живых людей и на предыдущем шаге умер воин j. Чтобы найти следующего, будем бежать по массиву, отсчитывая живых и пропуская мертвых. Тот человек, на котором мы насчитаем k % M и должен умереть следующим. Через N — 1 шаг останется один человек.

Рекурсивное решение

Простейшее моделирование  будет работать O ( ). Используя дерево отрезков, можно произвести моделирование за . Однако попытаемся найти закономерность, выражающую ответ для задачи (N,K) через решение предыдущих задач. С помощью моделирования построим таблицу значений, скажем, приведенную ниже.

Табличка
	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2	1	2	1
3	3	3	2	2	1	1	3	3	2	2
4	4	1	1	2	2	3	2	3	3	4
5	5	3	4	1	2	4	4	1	2	4
6	6	5	1	5	1	4	5	3	5	2
7	7	7	4	2	6	3	5	4	7	5
8	8	1	7	6	3	1	4	4	8	7
9	9	3	1	1	8	7	2	3	8	8
10	10	5	4	5	3	3	9	1	7	8

И здесь достаточно отчётливо видна следующая закономерность:

 joseph (n, k) = ( joseph (n-1, k) + k - 1 ) % n + 1;

 joseph (1, k) = 1

(здесь индексация  с единицы несколько портит  элегантность формулы)

Итак, мы нашли решение  задачи Иосифа Флавия, работающее за итераций.

Пример

С целью подробного объяснения возможных ситуаций, которые  могут возникнуть в ходе решения, упростим исходную задачу и рассмотрим случай № 1, причем, уменьшим круг солдат с сорока одного (сорок солдат, в  том числе Иосиф) до десяти и предположим, что вместо каждого третьего солдата  должен умереть каждый второй. В  результате будем рассматривать  круг солдат, изображенный на рис 1.

Рис 1. Круг из 10-ти солдат,в котором

должен «умереть» каждый второй

Если производить  отсчет от 1-го солдата в круге, то порядок удаления будет следующим: 2, 4, 6, 8, 10, 3, 7, 1, 9. Солдат под номером 5 – в конечном итоге остается в живых.

Этапы «уничтожения»  солдат из круга графически представлены на рис 2 - 4.

Рис 2. 1-й этап удаления	Рис 3. 2-й этап удаления	Рис 4. 3-й этап удаления

Нет ничего проще  рассмотрения конкретной ситуации и  определения результатов, используя  предопределенные условия. Задача состоит  в том, чтобы установить зависимости  между параметрами k, n (где n - это количество людей в круге, k – служит для определения каждого k-го солдата для «исключения» из круга), и решить задачу независимо от того, сколько солдат стоят в круге. Попробуем вывести общие формулы для решения задачи с любыми входными параметрами (на вход подаются значения k и n). Для этого определяем функцию F(n), где F(n) - возвращает номер победителя. Сразу возникает первое предположение, что F(n) может быть в пределах F(n) = n / 2, что верно при n = 10 или n = 2. Однако при n = 4 F(4) = 1, что доказывает неправильность рассуждений. Следующее замечание из рассмотренной выше ситуации: полученный результат – нечетный номер, независимо от значения n, так произошло вследствие того, что в ходе 1-го этапа – были убраны все четные номера. Также следует учесть тот факт, что при n = 1 F(1) = 1. Предположив, что на входе солдат = 2n. То, что остается после 1-го этапа показано на рис. 5.

Рис. 5 – 1-й этап при количестве солдат в круге 2n

Наблюдается аналогичная  ситуация и при 2n-1 – солдатах на входе (рис.6). Однако вводится поправка- уменьшение на единицу и увеличение F(n) в 2 раза.

Рис. 6. солдат в круге 2n - 1

Из чего можно  вывести формулу F(2n) = 2*F(n) – 1 (для всех n > 1 ). Рассмотрим случай № 2, приняв во внимание тот факт, что на вход подаются 2n + 1 число солдат (т.е. нечетное количество солдат). После проведения 1-го этапа «исключения» солдат из круга получится нечто, приведенное на рис.7.

Рис. 7 – 1-й этап при количестве солдат в круге 2n + 1

Из чего можно  вывести формулу F(2n +1) = 2*F(n) + 1 (для всех n > 1 ). Сведем все рассмотренные ситуации и запишем все случаи в виде системы, позволяющей определить значение функции F(n) - для любых значений n:

Выведенные выше формулы могут быть применены  и для решения исходной задачи – Иосифа Флавия. А именно: F(2^m + k) = 2k + 1; для любого m любого k.

Решение на основе двоичного  представления n

Рассмотрим двоичные представлениям величин n и J(n):

n = bm*2^m + bm-1*2^(m-1) + … + b1*2 + b0

где каждое bi равно 0 или 1, причем старший бит bm равен 1. Вспоминая, что n=2^m+k, последовательно получаем: 
n = (1 bm-1 … b1 b0)2 
k = (0 bm-1 … b1 b0)2 
(т.к. k= n−2^m = 2^m + bm-1*2^(m-1) + … + b1*2 + b0 − 2^m = 0∙2^m + bm-12^(m-1) + …+ b1*2 + b0) 
2k = (bm-1 … b1 b0 0)2 
(т.к. 2 k=2(bm-1*2^(m-1) +bm-2*2^(m-2) …+ b1*2 + b0)=bm-1*2^m + bm-2*2^(m-1) + … + b1*2^2 + b0*2+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 
т.е. J(n) получается путем циклического сдвига двоичного представления n влево на одну позицию.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Задача о ханойской башне.

 

Рассмотрим сначала маленькую  изящную головоломку под названием  ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой  восемь дисков, нанизанных в порядке  уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить  всю башню на один из других колышков, перенося каждый раз только один диск, и не помещая больший диск на меньший.  
Будем решать эту задачу в общем виде, т.е. посмотрим, что будет в случае n дисков.  
Будем говорить, что T_n есть минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка.  
Рассмотрим крайние случаи: Т₀=0, T₁=1, T₂=3, T₃=7. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n−1) меньших дисков на любой из колышков (что требует Т_n-1 перекладываний), затем перекладываем самый большой диск (одно перекладывание ) и, наконец, помещаем (n−1) меньших дисков обратно на самый большой диск (еще Т_n-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 2T_n-1+1 перекладываний (т.е. достаточно перекладываний):  T_n ≤ 2T_n-1+1.  
Сейчас покажем, что необходимо 2T_n-1+1 перекладываний. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем, (n−1) меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере Т_n-1  перекладываний. Самый большой диск можно перекладывать и более одного раза. Но после перемещения самого большого диска в последний раз мы обязаны поместить (n−1) меньших дисков (которые опять должны находиться на одном колышке) обратно на наибольший диск, что также требует Т_n-1  перекладываний. Следовательно, T_n ≥ 2T_n-1+1.  
Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:  

(1)

 

     Т₀=0                                               
     T_n = 2T_n-1+1    при n>0                                                                                                                                
При достаточно большом n для вычисления Т_n потребуется слишком много времени, поэтому получим Т_n в простой, компактной, «замкнутой форме», что позволит вычислить Т_n быстро.  
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна).  
Вычислим:  Т₃=2∙3+1=7; Т₄=2∙7+1; Т₅=2∙15+1; Т₆=2∙31+1=63. Теперь можно сделать предположение, что

 
                                   Т_n =2ⁿ − 1  при n≥0.                                            (2)

 
Докажем методом математической индукции по числу n:  
1)          База:  n=0,     Т₀=2⁰–1=1–1=0 (верно);  
2)          Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n: Т_n= 2T_n-1+1  2(2^n-1−1)+1 = 2∙2^n-1−2+1 = 2ⁿ − 1  
Из пунктов 1 и 2 следует:   при n≥0      Т_n = 2ⁿ − 1   

 
Второй способ решения.  
К обеим частям соотношения (1) прибавим 1:  
                                                       Т₀+1 = 1,  
                                                   Т_n+1 = 2T_n-1+2      при n>0.     
Обозначим U_n = T_n+1, тогда получим  
                                                      U₀ = 1  
                                                  U_n = 2U_n-1       при n>0.  
Решением этой рекурсии есть U_n=2ⁿ; следовательно Т_n = 2ⁿ−1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

1

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

2

L1=2