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

Задача Иосифа Флавия — задача, входящая в одну из ранних работ по занимательной математике (1612 года) Баше де Мезириака. Задача заключается в следующем: по кругу стоит 41 воин, начиная с первого воина они убивают каждого третьего. Спрашивается, в каком месте нужно встать, чтобы остаться последним выжившим. В более общей формулировке участвует n воинов, которые считаются по кругу, и убивают каждого m-го. Название задачи восходит к истории, случившейся с Иосифом Флавием во время Иудейской войны.

История

Эта задача известна с 1612 года, когда французский математик Баше опубликовал эту задачу в своём сборнике Problem es Plaisants. Сюжет задачи основан на истории, описанной Иосифом Флавием в своём историческом труде «Иудейская война».

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

Далее Иосиф (говоря о себе в третьем лице) пишет: Шаблон:Quote

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

Задача вдохновила Станислава Улама на создание понятия счастливого числа.

На решении задачи Иосифа для $m=2$ основан фокус «Love Ritual», созданный испанским фокусником Шаблон:Iw, который показывают Пенн и Теллер.

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

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

Для $m=2$ имеем

$k(n)=\{\begin{array}{cc}1,& \text{если }n=1\\ 1+(k(n-1)+1)modn,& \text{если }n>1\end{array}$

Для $m=3$ имеем

$k(n)=\{\begin{array}{cc}1,& \text{если }n=1\\ 1+(k(n-1)+2)modn,& \text{если }n>1\end{array}$

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

$\mathrm{\forall }m>0:k(n,m)=\{\begin{array}{cc}1,& \text{если }n=1\\ 1+(k(n-1,m)+m-1)modn,& \text{если }n>1\end{array}$

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

$k(n)=\{\begin{array}{cc}1,& \text{если }n=1\\ 2k\left(\frac{n}{2}\right)-1,& \text{если }n>1\text{ четное}\\ 2k\left(\frac{n-1}{2}\right)+1,& \text{если }n>1\text{ нечетное}\end{array}$

Решение в виде формулы

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

Для $m=2$ существует простая формула:

$k(n)=2\cdot (n-2^{\lfloor {\log }_{2}n\rfloor })+1$

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

Решение перебором

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

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

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

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

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

Пример

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

Представление решения для случая убийства каждого 2-го через двоичную запись

Рассмотрим двоичные представлениям величин n и F(n): $n=b_m\cdot 2^m+b_{m-1}\cdot 2^{m-1}+...+b_1\cdot 2+b_0$, где каждое $b_i$ равно 0 или 1, причем старший бит $b_m$ равен 1. Вспоминая, что $n=2^m+k$, последовательно получаем:

$n=(1b_{m-1}...b_1{b}_0{)}_2$

$k=(0b_{m-1}...b_1{b}_0{)}_2$

(так как $k=n-2^m=2^m+b_{m-1}\cdot 2^{m-1}+\dots +b_1\cdot 2+b_0-2^m=0\cdot 2^m+b_{m-1}\cdot 2^{m-1}+\dots +b_1\cdot 2+b_0$)

$2k=(b_{m-1}\dots b_1{b}_{0}0{)}_2$

(так как $2k=2(b_{m-1}\cdot 2^{m-1}+b_{m-2}\cdot 2^{m-2}+\dots +b_1\cdot 2+b_0)=b_{m-1}\cdot 2^m+b_{m-2}\cdot 2^{m-1}+\dots +b_1\cdot 2^2+b_0\cdot 2+0$)

$2k+1=(b_{m-1}\dots b_1{b}_{0}1{)}_2$

$F(n)=(b_{m-1}\dots b_1{b}_0{b}_m{)}_2$

(так как $F(n)=2k+1$ и $b_m=1$)
Таким образом, мы получили, что

$F((b_m{b}_{m-1}\dots b_1{b}_0{)}_2)=(b_{m-1}\dots b_1{b}_0{b}_m{)}_2$,

то есть F(n) получается путём циклического сдвига двоичного представления n влево на одну позицию.

Литература

• Шаблон:Статья
• Шаблон:Книга