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

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

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

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

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

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

Для <math>m=2</math> имеем

<math> k(n)= \begin{cases} 1, & \mbox{if }n= 1 \\ 1+(k(n-1)+1) \mod {n}, & \mbox {if }n>1\end{cases}</math>.

Для <math>m=3</math> имеем

<math> k(n)= \begin{cases} 1, & \mbox{if }n= 1 \\ 1+(k(n-1)+2) \mod {n}, & \mbox {if }n>1\end{cases}</math>.

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

<math> \forall m>0: k(n,m)= \begin{cases} 1, & \mbox{if }n= 1 \\ 1+(k(n-1,m)+m-1) \mod {n}, & \mbox {if }n>1\end{cases}</math>.

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

<math>

k(n)= \begin{cases} 1, & \mbox{if }n= 1 \\ 2k\left( \frac{n}{2} \right)-1, & \mbox{if }n>1\mbox{ is even} \\ 2k\left( \frac{n-1}{2} \right)+1, & \mbox{if }n>1\mbox{ is odd} \end{cases} </math>.

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

При программировании приведенные выше рекуррентные соотношения дают вычислительную сложность <math>O(n)</math> и <math>O(\log n)</math> соответственно. Получение решения в замкнутой форме должно приводить к алгоритмам в которых вычислительная сложность минимальна — <math>O(1)</math>, т. е. вообще не зависит от <math>n</math> и <math>m</math>. (Длина записи представления чисел в системе счисления не учитывается). Построение таких формул крайне желательно и для данной задачи. Например, для <math>m=2</math> не сложно получить формулу

<math> k(n)=2\cdot\left(n-2^{\lfloor \log_2 n \rfloor}\right)+1</math>

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

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

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

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

Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 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 (<math>N^2</math>). Используя дерево отрезков, можно произвести моделирование за <math>O(N log N)</math>. Однако попытаемся найти закономерность, выражающую ответ для задачи (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

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

Итак, мы нашли решение задачи Иосифа Флавия, работающее за <math>O(N)</math> итераций.

Пример

С целью подробного объяснения возможных ситуаций, которые могут возникнуть в ходе решения, упростим исходную задачу и рассмотрим случай № 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 влево на одну позицию.

Литература

• М. А. Алексеев [home.gwu.edu/~maxal/josephus.pdf Задача Иосифа Флавия] // Империя Математики. — 2001. — № 2. — С. 22—28.
• Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7.

Отрывок, характеризующий Задача Иосифа Флавия

– Ну, что, Леля? – обратился он тотчас же к дочери с тем небрежным тоном привычной нежности, который усвоивается родителями, с детства ласкающими своих детей, но который князем Василием был только угадан посредством подражания другим родителям.
И он опять обратился к Пьеру.
– Сергей Кузьмич, со всех сторон , – проговорил он, расстегивая верхнюю пуговицу жилета.
Пьер улыбнулся, но по его улыбке видно было, что он понимал, что не анекдот Сергея Кузьмича интересовал в это время князя Василия; и князь Василий понял, что Пьер понимал это. Князь Василий вдруг пробурлил что то и вышел. Пьеру показалось, что даже князь Василий был смущен. Вид смущенья этого старого светского человека тронул Пьера; он оглянулся на Элен – и она, казалось, была смущена и взглядом говорила: «что ж, вы сами виноваты».
«Надо неизбежно перешагнуть, но не могу, я не могу», думал Пьер, и заговорил опять о постороннем, о Сергее Кузьмиче, спрашивая, в чем состоял этот анекдот, так как он его не расслышал. Элен с улыбкой отвечала, что она тоже не знает.
Когда князь Василий вошел в гостиную, княгиня тихо говорила с пожилой дамой о Пьере.
– Конечно, c'est un parti tres brillant, mais le bonheur, ma chere… – Les Marieiages se font dans les cieux, [Конечно, это очень блестящая партия, но счастье, моя милая… – Браки совершаются на небесах,] – отвечала пожилая дама.
Князь Василий, как бы не слушая дам, прошел в дальний угол и сел на диван. Он закрыл глаза и как будто дремал. Голова его было упала, и он очнулся.
– Aline, – сказал он жене, – allez voir ce qu'ils font. [Алина, посмотри, что они делают.]
Княгиня подошла к двери, прошлась мимо нее с значительным, равнодушным видом и заглянула в гостиную. Пьер и Элен так же сидели и разговаривали.
– Всё то же, – отвечала она мужу.
Князь Василий нахмурился, сморщил рот на сторону, щеки его запрыгали с свойственным ему неприятным, грубым выражением; он, встряхнувшись, встал, закинул назад голову и решительными шагами, мимо дам, прошел в маленькую гостиную. Он скорыми шагами, радостно подошел к Пьеру. Лицо князя было так необыкновенно торжественно, что Пьер испуганно встал, увидав его.
– Слава Богу! – сказал он. – Жена мне всё сказала! – Он обнял одной рукой Пьера, другой – дочь. – Друг мой Леля! Я очень, очень рад. – Голос его задрожал. – Я любил твоего отца… и она будет тебе хорошая жена… Бог да благословит вас!…
Он обнял дочь, потом опять Пьера и поцеловал его дурно пахучим ртом. Слезы, действительно, омочили его щеки.
– Княгиня, иди же сюда, – прокричал он.
Княгиня вышла и заплакала тоже. Пожилая дама тоже утиралась платком. Пьера целовали, и он несколько раз целовал руку прекрасной Элен. Через несколько времени их опять оставили одних.
«Всё это так должно было быть и не могло быть иначе, – думал Пьер, – поэтому нечего спрашивать, хорошо ли это или дурно? Хорошо, потому что определенно, и нет прежнего мучительного сомнения». Пьер молча держал руку своей невесты и смотрел на ее поднимающуюся и опускающуюся прекрасную грудь.
– Элен! – сказал он вслух и остановился.
«Что то такое особенное говорят в этих случаях», думал он, но никак не мог вспомнить, что такое именно говорят в этих случаях. Он взглянул в ее лицо. Она придвинулась к нему ближе. Лицо ее зарумянилось.
– Ах, снимите эти… как эти… – она указывала на очки.
Пьер снял очки, и глаза его сверх той общей странности глаз людей, снявших очки, глаза его смотрели испуганно вопросительно. Он хотел нагнуться над ее рукой и поцеловать ее; но она быстрым и грубым движеньем головы пeрехватила его губы и свела их с своими. Лицо ее поразило Пьера своим изменившимся, неприятно растерянным выражением.
«Теперь уж поздно, всё кончено; да и я люблю ее», подумал Пьер.
– Je vous aime! [Я вас люблю!] – сказал он, вспомнив то, что нужно было говорить в этих случаях; но слова эти прозвучали так бедно, что ему стало стыдно за себя.
Через полтора месяца он был обвенчан и поселился, как говорили, счастливым обладателем красавицы жены и миллионов, в большом петербургском заново отделанном доме графов Безухих.


Старый князь Николай Андреич Болконский в декабре 1805 года получил письмо от князя Василия, извещавшего его о своем приезде вместе с сыном. («Я еду на ревизию, и, разумеется, мне 100 верст не крюк, чтобы посетить вас, многоуважаемый благодетель, – писал он, – и Анатоль мой провожает меня и едет в армию; и я надеюсь, что вы позволите ему лично выразить вам то глубокое уважение, которое он, подражая отцу, питает к вам».)
– Вот Мари и вывозить не нужно: женихи сами к нам едут, – неосторожно сказала маленькая княгиня, услыхав про это.
Князь Николай Андреич поморщился и ничего не сказал.
Через две недели после получения письма, вечером, приехали вперед люди князя Василья, а на другой день приехал и он сам с сыном.
Старик Болконский всегда был невысокого мнения о характере князя Василья, и тем более в последнее время, когда князь Василий в новые царствования при Павле и Александре далеко пошел в чинах и почестях. Теперь же, по намекам письма и маленькой княгини, он понял, в чем дело, и невысокое мнение о князе Василье перешло в душе князя Николая Андреича в чувство недоброжелательного презрения. Он постоянно фыркал, говоря про него. В тот день, как приехать князю Василью, князь Николай Андреич был особенно недоволен и не в духе. Оттого ли он был не в духе, что приезжал князь Василий, или оттого он был особенно недоволен приездом князя Василья, что был не в духе; но он был не в духе, и Тихон еще утром отсоветывал архитектору входить с докладом к князю.
– Слышите, как ходит, – сказал Тихон, обращая внимание архитектора на звуки шагов князя. – На всю пятку ступает – уж мы знаем…
Однако, как обыкновенно, в 9 м часу князь вышел гулять в своей бархатной шубке с собольим воротником и такой же шапке. Накануне выпал снег. Дорожка, по которой хаживал князь Николай Андреич к оранжерее, была расчищена, следы метлы виднелись на разметанном снегу, и лопата была воткнута в рыхлую насыпь снега, шедшую с обеих сторон дорожки. Князь прошел по оранжереям, по дворне и постройкам, нахмуренный и молчаливый.
– А проехать в санях можно? – спросил он провожавшего его до дома почтенного, похожего лицом и манерами на хозяина, управляющего.
– Глубок снег, ваше сиятельство. Я уже по прешпекту разметать велел.
Князь наклонил голову и подошел к крыльцу. «Слава тебе, Господи, – подумал управляющий, – пронеслась туча!»
– Проехать трудно было, ваше сиятельство, – прибавил управляющий. – Как слышно было, ваше сиятельство, что министр пожалует к вашему сиятельству?
Князь повернулся к управляющему и нахмуренными глазами уставился на него.
– Что? Министр? Какой министр? Кто велел? – заговорил он своим пронзительным, жестким голосом. – Для княжны, моей дочери, не расчистили, а для министра! У меня нет министров!
– Ваше сиятельство, я полагал…
– Ты полагал! – закричал князь, всё поспешнее и несвязнее выговаривая слова. – Ты полагал… Разбойники! прохвосты! Я тебя научу полагать, – и, подняв палку, он замахнулся ею на Алпатыча и ударил бы, ежели бы управляющий невольно не отклонился от удара. – Полагал! Прохвосты! – торопливо кричал он. Но, несмотря на то, что Алпатыч, сам испугавшийся своей дерзости – отклониться от удара, приблизился к князю, опустив перед ним покорно свою плешивую голову, или, может быть, именно от этого князь, продолжая кричать: «прохвосты! закидать дорогу!» не поднял другой раз палки и вбежал в комнаты.
Перед обедом княжна и m lle Bourienne, знавшие, что князь не в духе, стояли, ожидая его: m lle Bourienne с сияющим лицом, которое говорило: «Я ничего не знаю, я такая же, как и всегда», и княжна Марья – бледная, испуганная, с опущенными глазами. Тяжелее всего для княжны Марьи было то, что она знала, что в этих случаях надо поступать, как m lle Bourime, но не могла этого сделать. Ей казалось: «сделаю я так, как будто не замечаю, он подумает, что у меня нет к нему сочувствия; сделаю я так, что я сама скучна и не в духе, он скажет (как это и бывало), что я нос повесила», и т. п.
Князь взглянул на испуганное лицо дочери и фыркнул.
– Др… или дура!… – проговорил он.
«И той нет! уж и ей насплетничали», подумал он про маленькую княгиню, которой не было в столовой.
– А княгиня где? – спросил он. – Прячется?…
– Она не совсем здорова, – весело улыбаясь, сказала m llе Bourienne, – она не выйдет. Это так понятно в ее положении.
– Гм! гм! кх! кх! – проговорил князь и сел за стол.
Тарелка ему показалась не чиста; он указал на пятно и бросил ее. Тихон подхватил ее и передал буфетчику. Маленькая княгиня не была нездорова; но она до такой степени непреодолимо боялась князя, что, услыхав о том, как он не в духе, она решилась не выходить.
– Я боюсь за ребенка, – говорила она m lle Bourienne, – Бог знает, что может сделаться от испуга.
Вообще маленькая княгиня жила в Лысых Горах постоянно под чувством страха и антипатии к старому князю, которой она не сознавала, потому что страх так преобладал, что она не могла чувствовать ее. Со стороны князя была тоже антипатия, но она заглушалась презрением. Княгиня, обжившись в Лысых Горах, особенно полюбила m lle Bourienne, проводила с нею дни, просила ее ночевать с собой и с нею часто говорила о свекоре и судила его.