проблема Иосифа Флавия

Математический вопрос на счет

Интерпретация Клодом Гаспаром Баше де Мезириаком задачи Иосифа Флавия с 41 солдатом и шагом 3, показывающая, что позиции 16 и 31 убиваются последними — время движется внутрь по спирали, зеленые точки обозначают живых солдат, серые мертвые солдаты, а крестики — убийства

В информатике и математике проблема Иосифа (или перестановка Иосифа ) — это теоретическая проблема, связанная с определенной игрой-счётом . Такие игры используются для выбора человека из группы, например, eeny, meeny, miny, moe .

Рисунок для последовательности задач Иосифа Флавия для 500 человек и пропускаемого значения 6. Горизонтальная ось — номер человека. Вертикальная ось (сверху вниз) — время (номер цикла). Живой человек нарисован зеленым цветом, мертвый — черным. ^[1]

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

Задача — учитывая количество людей, начальную точку, направление и количество пропущенных объектов — выбрать позицию в начальном круге, чтобы избежать казни.

История

Задача названа в честь Иосифа Флавия , еврейского историка и лидера, жившего в I веке. Согласно рассказу Иосифа Флавия об осаде Йодфата , он и его 40 солдат были заперты в пещере римскими солдатами . Они предпочли самоубийство пленению и остановились на последовательном методе совершения самоубийства путем жеребьевки. Иосиф утверждает, что по счастливой случайности или, возможно, по воле Бога, он и еще один человек остались до конца и сдались римлянам, а не покончили с собой. Это история, приведенная в Книге 3, Главе 8, Части 7 «Иудейской войны » Иосифа Флавия ( писавшего о себе в третьем лице ):

Однако в этом крайнем бедствии он не был лишен своей обычной проницательности; но, доверившись провидению Божьему, он подверг свою жизнь опасности [следующим образом]: "И теперь", сказал он, "поскольку среди вас решено, что вы умрете, давайте предоставим нашу общую смерть определению жребия. Тот, кому жребий выпадет первым, пусть будет убит тем, кому выпадет второй жребий, и таким образом удача будет совершать свой прогресс через всех нас; и никто из нас не погибнет от своей собственной правой руки, ибо было бы несправедливо, если бы, когда остальные уйдут, кто-то раскаялся и спас себя". Это предложение показалось им очень справедливым; и когда он убедил их решить этот вопрос жребием, он вытянул один из жребиев и для себя. Тот, у кого был первый жребий, обнажил свою шею тому, у кого был следующий, как будто предполагая, что генерал умрет среди них немедленно; ибо они думали, что смерть, если Иосиф умрет вместе с ними, слаще жизни; но он был с другим, оставленным до последнего, должны ли мы сказать, что это произошло так случайно, или по провидению Божию. И поскольку он очень не желал ни быть осужденным жребием, ни, если бы он был оставлен до последнего, обагрить свою правую руку кровью своих соотечественников, он убедил его довериться своей верности ему и жить так же хорошо, как и он сам.

—  Иосиф Флавий, стр. 579, «Иудейские войны», книга III, гл. 8, параграф 7

Детали механизма, использованного в этом подвиге, довольно расплывчаты. Согласно Джеймсу Дауди и Майклу Мейсу, ^[2] в 1612 году Клод Гаспар Баше де Мезириак предложил конкретный механизм расстановки людей в круг и подсчета по трое для определения порядка выбывания. ^[3] Эта история часто повторялась, и конкретные детали значительно различаются от источника к источнику. Например, Израиль Натан Херштейн и Ирвинг Каплански (1974) заставляют Иосифа и 39 товарищей стоять в кругу, и каждый седьмой человек выбывает. ^[4] Историю проблемы можно найти в письме С. Л. Забелла редактору Fibonacci Quarterly . ^[5]

Что касается преднамеренности, Иосиф Флавий спросил: «Должны ли мы отнести это на счет божественного провидения или просто удачи?» ^[6] Но сохранившаяся славянская рукопись Иосифа Флавия рассказывает другую историю: что он «хитро подсчитал числа и таким образом сумел обмануть всех остальных». ^{[6] [7]} У Иосифа был сообщник; проблема тогда заключалась в том, чтобы найти места двух последних оставшихся в живых (чей заговор обеспечил бы их выживание). Утверждается, что он поместил себя и другого человека на 31-е и 16-е места соответственно (для k = 3 ниже). ^[8]

Варианты и обобщения

Вариант задачи Иосифа Флавия с 30 людьми и шагом 9 — время движется внутрь по спирали, зеленые точки обозначают живых солдат, серые — мертвых солдат, а кресты — убийства.

Средневековая версия задачи Иосифа Флавия включает 15 турок и 15 христиан на борту корабля во время шторма, который затонет, если только половина пассажиров не будет выброшена за борт. Все 30 встают в круг, и каждый девятый человек должен быть выброшен в море. Христианам нужно определить, где встать, чтобы гарантировать, что будут выброшены только турки. ^[9] В других версиях роли турок и христиан меняются местами.

Грэм, Кнут и Паташник 1989, стр. 8 описывают и изучают «стандартный» вариант: определяют, где находится последний выживший, если в начале игры есть n человек, а каждый второй человек ( k = 2 ниже) выбывает.

Обобщение этой проблемы выглядит следующим образом. Предполагается, что каждый m -й человек будет казнен из группы размером n , в которой p -й человек является выжившим. Если в круг добавляется x человек, то выживший находится в p + mx -й позиции, если она меньше или равна n + x . Если x - наименьшее значение, для которого p + mx > n + x , то выживший находится в позиции ( p + mx ) − ( n + x ) . ^[10]

Решение

Предпоследнее (розовое) и конечное (ультрамариновое) места в задаче Иосифа Флавия для различных размеров групп, n и размеров шагов, k . В файле SVG наведите курсор на значения, чтобы увидеть полный порядок убийства.

В дальнейшем обозначает количество людей в начальном круге, а обозначает количество для каждого шага, то есть люди пропускаются и выполняется -й. Люди в круге пронумерованы от до , начальная позиция и подсчет ведется включительно . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 1}$

к= 2

Задача решается явно, когда каждый второй человек будет убит (каждый человек убивает человека слева или справа), т. е . . (Для более общего случая решение изложено ниже.) Решение выражается рекурсивно . Пусть обозначает положение выжившего, когда изначально n человек (и ). При первом прохождении круга все четные люди умирают. При втором прохождении круга умирает новый 2-й человек, затем новый 4-й человек и т. д.; как будто первого прохождения круга не было. ${\displaystyle k=2}$ ${\displaystyle k\neq 2}$ ${\displaystyle f(n)}$ ${\displaystyle k=2}$

Если изначальное количество людей было четным, то человек в позиции x во время второго обхода круга изначально находился в позиции (для каждого выбора x ). Пусть . Человек, который теперь выживет, изначально находился в позиции . Это дает рекуррентное соотношение ${\displaystyle 2x-1}$ ${\displaystyle n=2j}$ ${\displaystyle f(j)}$ ${\displaystyle 2f(j)-1}$

${\displaystyle f(2j)=2f(j)-1\;.}$

Если изначальное количество людей было нечетным , то можно считать, что человек 1 умирает в конце первого раза по кругу. Опять же, во время второго раза по кругу умирает новый 2-й человек, затем новый 4-й человек и т. д. В этом случае человек в позиции x изначально находился в позиции . Это дает повторение ${\displaystyle 2x+1}$

${\displaystyle f(2j+1)=2f(j)+1\;.}$

Если значения свести в таблицу и выявить закономерность ( OEIS : A006257 , также самый левый столбец синих чисел на рисунке выше): ${\displaystyle n}$ ${\displaystyle f(n)}$

Это предполагает, что является возрастающей нечетной последовательностью, которая перезапускается с всякий раз, когда индекс n является степенью 2 . Следовательно, если m и l выбраны так, что и , то . Очевидно, что значения в таблице удовлетворяют этому уравнению. Или можно подумать, что после того, как l человек погибнут, останутся только люди, и это перейдет к первому человеку. Этот человек должен быть выжившим. Поэтому . Ниже приведено доказательство по индукции . ${\displaystyle f(n)}$ ${\displaystyle f(n)=1}$ ${\displaystyle n=2^{m}+l}$ ${\displaystyle 0\leq l<2^{m}}$ ${\displaystyle f(n)=2l+1}$ ${\displaystyle 2^{m}}$ ${\displaystyle 2l+1}$ ${\displaystyle f(n)=2l+1}$

Теорема: Если и , то . ${\displaystyle n=2^{m}+l}$ ${\displaystyle 0\leq l<2^{m}}$ ${\displaystyle f(n)=2l+1}$

Доказательство: Сильная индукция используется по n . Базовый случай истинен. Случаи рассматриваются отдельно, когда n четное и когда n нечетное. ${\displaystyle n=1}$

Если n четно, то выбираем и такие, что и . Заметим, что . имеет место, где второе равенство следует из предположения индукции. ${\displaystyle l_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle n/2=2^{m_{1}}+l_{1}}$ ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$ ${\displaystyle l_{1}=l/2}$ ${\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}$

Если n нечетно, то выбираем и такие, что и . Заметим, что . имеет место, где второе равенство следует из индукционного предположения. Это завершает доказательство. ${\displaystyle l_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$ ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$ ${\displaystyle l_{1}=(l-1)/2}$ ${\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}$

l можно решить, получив явное выражение для : ${\displaystyle f(n)}$

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

Наиболее элегантная форма ответа включает двоичное представление размера n : может быть получена однобитовым левым циклическим сдвигом самого n . Если n представлено в двоичном виде как , то решение дается как . Доказательство этого следует из представления n как или из приведенного выше выражения для . ${\displaystyle f(n)}$ ${\displaystyle n=1b_{1}b_{2}b_{3}\dots b_{m}}$ ${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$ ${\displaystyle 2^{m}+l}$ ${\displaystyle f(n)}$

Реализация: Если n обозначает количество людей, то безопасное положение задается функцией , где и . ${\displaystyle f(n)=2l+1}$ ${\displaystyle n=2^{m}+l}$ ${\displaystyle 0\leq l<2^{m}}$

Теперь, если число представлено в двоичном формате, первый бит обозначает , а остальные биты будут обозначать l . Например, когда ⁠ ⁠ , его двоичное представление будет: ${\displaystyle 2^{m}}$ ${\displaystyle n=41}$

п = 1 0 1 0 0 12 м = 1 0 0 0 0 0л = 0 1 0 0 1

/** * @param n количество людей, стоящих в круге * @return безопасное положение, которое переживет казнь * f(N) = 2L + 1, где N =2^M + L и 0 <= L < 2^M */ public int getSafePosition ( int n ) { // найти значение L для уравнения int valueOfL = n - Integer . highestOneBit ( n ); return 2 * valueOfL + 1 ; }              

Побитовый

Самый простой способ найти безопасную позицию — использовать побитовые операторы . В этом подходе сдвиг наиболее значимого бита набора n к наименее значимому биту вернет безопасную позицию. ^[11] Входные данные должны быть положительным целым числом .

п = 1 0 1 0 0 1п = 0 1 0 0 1 1

/** * @param n (41) количество людей, стоящих в круге * @return безопасное положение, которое переживет казнь */ public int getSafePosition ( int n ) { return ~ Integer . highestOneBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // Получить первый установленный бит | | Сдвиг влево n и инвертирование последнего бита // и взять его дополнение | | // | | // Умножить n на 2 | // Побитовое И для копирования битов, которые существуют в обоих операндах. }                

к= 3

В 1997 году Лоренц Хальбейзен и Норберт Хунгербюлер открыли замкнутую форму для случая . Они показали, что существует определенная константа ${\displaystyle k=3}$

${\displaystyle \alpha \approx 0.8111...}$

который может быть вычислен с произвольной точностью. Учитывая эту константу, выберите m как наибольшее целое число, такое что (это будет либо , либо ). Тогда последний выживший будет ${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m})\leq n}$ ${\displaystyle m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )}$ ${\displaystyle m^{\prime }-1}$

${\displaystyle f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2}$если округляется в большую сторону иначе ${\displaystyle 1)}$

для всех . ${\displaystyle n\geq 5}$

В качестве примера вычисления Хальбейзен и Хунгербюлер приводят (что на самом деле является оригинальной формулировкой проблемы Иосифа Флавия). Они вычисляют: ${\displaystyle n=41,k=3}$

${\displaystyle m^{\prime }\approx \operatorname {round} (\log _{3/2}41/0.8111)\approx \operatorname {round} (9.68)=10}$

${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47}$и поэтому ${\displaystyle m=9}$

${\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31}$(обратите внимание, что округление произведено в меньшую сторону)

${\displaystyle f(n)=3(41-31)+1=31}$

Это можно проверить, посмотрев на каждый последующий проход по числам.1 через41 :

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41

2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40.

2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38

2, 4, 11, 16, 22, 25, 31, 35

2, 4, 16, 22, 31, 35

4, 16, 31, 35

16, 31

31

Общий случай

Динамическое программирование используется для решения этой задачи в общем случае путем выполнения первого шага и последующего использования решения оставшейся задачи. Когда индекс начинается с единицы, то человек в смещается от первого человека в позицию , где n — общее количество людей. Пусть обозначает позицию выжившего. После того, как -й человек убит, остается круг , и следующий подсчет начинается с человека, номер которого в исходной задаче был . Позиция выжившего в оставшемся круге будет , если подсчет начинается с ; смещение этого с учетом того факта, что начальная точка — , дает рекуррентность ^[12] ${\displaystyle s}$ ${\displaystyle ((s-1){\bmod {n}})+1}$ ${\displaystyle f(n,k)}$ ${\displaystyle k}$ ${\displaystyle n-1}$ ${\displaystyle (k{\bmod {n}})+1}$ ${\displaystyle f(n-1,k)}$ ${\displaystyle 1}$ ${\displaystyle (k{\bmod {n}})+1}$

${\displaystyle f(n,k)=((f(n-1,k)+k-1){\bmod {n}})+1,{\text{ with }}f(1,k)=1\,,}$

который принимает более простую форму

${\displaystyle g(n,k)=(g(n-1,k)+k){\bmod {n}},{\text{ with }}g(1,k)=0}$

если позиции пронумерованы от до . ${\displaystyle 0}$ ${\displaystyle n-1}$

Этот подход имеет время выполнения , но для малых и больших есть другой подход. Второй подход также использует динамическое программирование, но имеет время выполнения . Он основан на рассмотрении убийства k -го, 2 k -го, ..., -го людей как одного шага, затем изменение нумерации. ^{[ необходима цитата ]} ${\displaystyle O(n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(k\log n)}$ ${\displaystyle (\lfloor n/k\rfloor k)}$

Этот улучшенный подход принимает форму

${\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\{\begin{Bmatrix}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}}+n&{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)<n{\bmod {k}}\\\lfloor {\frac {k(g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}})}{k-1}}\rfloor &{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n\\\end{cases}}}$

Ссылки

Цитаты

1. R.Ugalde, Laurence. "Проблема Иосифа в языке программирования Fōrmulæ". Fōrmulæ . Получено 26 июля 2021 г. .
2. Доуди и Мейс 1989, стр. 125.
3. Баше 1612, стр. 174.
4. Херштейн и Каплански 1974, стр. 121–126.
5. Забелл 1976, стр. 48, 51.
6. Коэн, Ричард. Создание истории: Рассказчики, сформировавшие прошлое , стр. 54 (Simon & Schuster 2022).
7. https://gustavus.edu/mcs/max/concrete-abstractions-pdfs/chapter3.pdf ^{[ пустой URL PDF ]}
8. Рауз Болл 1905, стр. 19.
9. Ньюман 1988, стр. 2403–2405.
10. Робинсон 1960, стр. 47–52.
11. «Проблема Иосифа с использованием побитовой операции (Java)». GitHub . 7 января 2018 г. Получено 7 января 2018 г.
12. Пак и Тейшейра, 2018, стр. 1–7.

Источники

• Баше, CG (1612 г.). Проблемы Plaisants ed Delectables qui se font par les Nombres (на французском языке).
• Грэм, Р. Л.; Кнут, Д. Э .; Паташник, О. (1989). Конкретная математика: основа компьютерной науки . Эддисон Уэсли. ISBN 978-0-201-14236-5.
• Herstein, IN; Kaplansky, I. (1974). Matters Mathematical . Harper and Row. ISBN 9780060428037.
• Иосиф Флавий (б. д.). Труды Иосифа Флавия: в трех томах; с иллюстрациями. Перевод Уильяма Уистона. Лондон: George Routledge & Sons.
• Ньюман, Дж. Р. (1988). Мир математики . Т. 4. Tempus.
• Пак, Джанг-Ву; Тейшейра, Рикардо (2018). «Проблема серийной казни Иосифа Флавия». Korean J. Math . 26 (1): 1–7. doi :10.11568/kjm.2018.26.1.1.
• Робинсон, У. Дж. (1960). «Проблема Иосифа Флавия». Math. Gaz . 44 (347): 47–52. doi :10.2307/3608532. JSTOR  3608532. S2CID  125735054.
• Рауз Болл, WW (1905). Математические развлечения и эссе (2-е изд.). Лондон: Macmillan.
• Забелл, С.Л. (1976). «Письмо редактору» (PDF) . Fibonacci Quarterly . 14 : 48–51.

Дальнейшее чтение

• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Глава 14: Расширение структур данных". Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 318. ISBN 0-262-03293-7.
• Дауди, Джеймс; Мейс, Майкл Э. (1989). «Перестановки Джозефа». Журнал комбинаторной математики и комбинаторных вычислений . 6 : 125–130.
• Халбайзен, Л.; Хунгербюлер, Н. (1997). «Проблема Иосифа Флавия». Дж. Теор. Номбрес Бордо . 9 (2): 303–318. дои : 10.5802/jtnb.204 .
• Якобчик, Ф. (1973). «Об обобщенной проблеме Иосифа Флавия». Glasow Math. J . 14 (2): 168–173. doi : 10.1017/S0017089500001919 . S2CID  122980022.
• Ллойд, Эррол Л. (1983). "Алгоритм O(n logm) для задачи Иосифа Флавия". J. Algor . 4 (3): 262–270. doi :10.1016/0196-6774(83)90025-1.
• Одлыжко, Эндрю М.; Вильф, Герберт С. (1991). «Функциональная итерация и проблема Иосифа Флавия». Glasgow Math. J . 33 (2): 235–240. doi : 10.1017/S0017089500008272 . S2CID  123160551.
• Ruskey, Frank; Williams, Aaron (2010). "The Feline Josephus Problem". Lect. Not. Comp. Sci . Lecture Notes in Computer Science. Vol. 6099. pp. 343–354. Bibcode : 2010LNCS.6099..343R. doi : 10.1007/978-3-642-13122-6_33. ISBN 978-3-642-13121-9.ВЕСЕЛЬЕ2010
• Ruskey, Frank; Williams, Aaron (2012). «Проблема Иосифа о кошках». Theory Comput. Syst . 50 : 20–34. CiteSeerX  10.1.1.157.2956 . doi :10.1007/s00224-011-9343-6. S2CID  2273820.
• Салливан, Шон; Инско, Эрик (2018). «Вариант проблемы кошачьего Иосифа». arXiv : 1803.11340 [math.CO].
• Терио, Николя (2001). «Обобщения проблемы Иосифа Флавия». Util. Math. (58): 161–173. CiteSeerX  10.1.1.164.2015 .
• Вудхаус, Дэвид (1973). «Расширенная проблема Иосифа Флавия». Rev. Mat. Hisp.-Amer . 33 (4): 207–218.

Внешние ссылки

• Игра Иосифа Флавия (Java Applet) в стиле cut-the-knot, позволяющая выбирать каждый n- ^й из 50 (максимум).
• Вайсштейн, Эрик В. «Проблема Иосифа». Математический мир .
• Проблема Иосифа Флавия - Numberphile на YouTube
• Обобщенная задача Иосифа Флавия