Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




04.03.2021


04.03.2021


04.03.2021


04.03.2021


01.03.2021





Яндекс.Метрика

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

28.01.2021

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

История

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

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

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

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

На решении задачи Иосифа для m = 2 {displaystyle m=2} основан фокус «Love Ritual», созданный испанским фокусником Вуди Арагоном, который показывают Пенн и Теллер.

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

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

Для m = 2 {displaystyle m=2} имеем

k ( n ) = { 1 , если  n = 1 1 + ( k ( n − 1 ) + 1 ) mod n , если  n > 1 {displaystyle k(n)={egin{cases}1,&{mbox{если }}n=11+(k(n-1)+1)mod {n},&{mbox{если }}n>1end{cases}}}

Для m = 3 {displaystyle m=3} имеем

k ( n ) = { 1 , если  n = 1 1 + ( k ( n − 1 ) + 2 ) mod n , если  n > 1 {displaystyle k(n)={egin{cases}1,&{mbox{если }}n=11+(k(n-1)+2)mod {n},&{mbox{если }}n>1end{cases}}}

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

∀ m > 0 : k ( n , m ) = { 1 , если  n = 1 1 + ( k ( n − 1 , m ) + m − 1 ) mod n , если  n > 1 {displaystyle forall m>0:k(n,m)={egin{cases}1,&{mbox{если }}n=11+(k(n-1,m)+m-1)mod {n},&{mbox{если }}n>1end{cases}}}

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

k ( n ) = { 1 , если  n = 1 2 k ( n 2 ) − 1 , если  n > 1  четное 2 k ( n − 1 2 ) + 1 , если  n > 1  нечетное {displaystyle k(n)={egin{cases}1,&{mbox{если }}n=12kleft({frac {n}{2}} ight)-1,&{mbox{если }}n>1{mbox{ четное}}2kleft({frac {n-1}{2}} ight)+1,&{mbox{если }}n>1{mbox{ нечетное}}end{cases}}}

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

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

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

k ( n ) = 2 ⋅ ( n − 2 ⌊ log 2 ⁡ n ⌋ ) + 1 {displaystyle k(n)=2cdot left(n-2^{lfloor log _{2}n floor } ight)+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 {displaystyle N^{2}} ). Используя дерево отрезков, можно произвести моделирование за O ( N l o g N ) {displaystyle O(NlogN)} . Однако попытаемся найти закономерность, выражающую ответ для задачи (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 ) {displaystyle O(N)} итераций.

Пример

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

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

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

Рассмотрим конкретную ситуацию и определим результаты, используя предопределенные условия. Задача состоит в том, чтобы установить зависимости между параметрами 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.

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

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

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

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

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

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

n = ( 1 b m − 1 . . . b 1 b 0 ) 2 {displaystyle n=(1,b_{m-1}...b_{1}b_{0})_{2}} k = ( 0 b m − 1 . . . b 1 b 0 ) 2 {displaystyle k=(0,b_{m-1}...b_{1}b_{0})_{2}}

(так как k = n − 2 m = 2 m + b m − 1 ⋅ 2 m − 1 + … + b 1 ⋅ 2 + b 0 − 2 m = 0 ⋅ 2 m + b m − 1 ⋅ 2 m − 1 + … + b 1 ⋅ 2 + b 0 {displaystyle k=n-2^{m}=2^{m}+b_{m-1}cdot 2^{m-1}+ldots +b_{1}cdot 2+b_{0}-2^{m}=0cdot 2^{m}+b_{m-1}cdot 2^{m-1}+ldots +b_{1}cdot 2+b_{0}} )

2 k = ( b m − 1 … b 1 b 0 0 ) 2 {displaystyle 2k=(b_{m-1}ldots b_{1}b_{0}0)_{2}}

(так как 2 k = 2 ( b m − 1 ⋅ 2 m − 1 + b m − 2 ⋅ 2 m − 2 + … + b 1 ⋅ 2 + b 0 ) = b m − 1 ⋅ 2 m + b m − 2 ⋅ 2 m − 1 + … + b 1 ⋅ 2 2 + b 0 ⋅ 2 + 0 {displaystyle 2k=2(b_{m-1}cdot 2^{m-1}+b_{m-2}cdot 2^{m-2}+ldots +b_{1}cdot 2+b_{0})=b_{m-1}cdot 2^{m}+b_{m-2}cdot 2^{m-1}+ldots +b_{1}cdot 2^{2}+b_{0}cdot 2+0} )

2 k + 1 = ( b m − 1 … b 1 b 0 1 ) 2 {displaystyle 2k+1=(b_{m-1}ldots b_{1}b_{0}1)_{2}} F ( n ) = ( b m − 1 … b 1 b 0 b m ) 2 {displaystyle F(n)=(b_{m-1}ldots b_{1}b_{0}b_{m})_{2}}

(так как F ( n ) = 2 k + 1 {displaystyle F(n)=2k+1} и b m = 1 {displaystyle b_{m}=1} )
Таким образом, мы получили, что

F ( ( b m b m − 1 … b 1 b 0 ) 2 ) = ( b m − 1 … b 1 b 0 b m ) 2 {displaystyle F((b_{m}b_{m-1}ldots b_{1}b_{0})_{2})=(b_{m-1}ldots b_{1}b_{0}b_{m})_{2}} ,

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