Проблема Джозефа

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

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

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

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

Проблема (с учетом количества людей, начальной точки, направления и числа, которое нужно пропустить) состоит в том, чтобы выбрать позицию в начальном круге, чтобы избежать выполнения.

История

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

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

- Иосиф Флавий , с. 579, Войны евреев, Книга III, Гл. 8, пункт 7

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

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

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

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

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

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

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

Решение

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

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

к = 2

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

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

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

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

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

Когда значения сведены в таблицу $n$ и $f(n)$ появляется шаблон ( OEIS : A006257 , также крайний левый столбец синих чисел на рисунке выше):

н	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

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

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

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

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

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

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

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

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

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

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

n    = 1   0   1   0   0   1
2m   = 1   0   0   0   0   0
l    =     0   1   0   0   1

/**
 * @param n the number of people standing in the circle
 * @return the safe position who will survive the execution 
 *   f(N) = 2L + 1 where N =2^M + L and 0 <= L < 2^M
 */
public int getSafePosition(int n) {
	// find value of L for the equation
	int valueOfL = n - Integer.highestOneBit(n);
	return 2 * valueOfL  + 1;
}

Побитовый

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

n    = 1   0   1   0   0   1
n    = 0   1   0   0   1   1

/**
 * @param n (41) the number of people standing in the circle
 * @return the safe position who will survive the execution 
 */
public int getSafePosition(int n) {
    return ~Integer.highestOneBit(n*2) & ((n<<1) | 1);
    //     ---------------------- ---  | ------------
    //     Get the first set bit   |   | Left Shift n and flipping the last bit
    //    and take its complement  |   |
    //                             |   |
    //                Multiply n by 2  |
    //                         Bitwise And to copy bits exists in both operands.
}

к = 3

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

$\alpha \approx 0.8111...$

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

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

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

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

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

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

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

$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

Общий случай

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

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

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

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

если позиции нумеруются от $0$ к $n-1$ вместо.

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

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

$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}}$

Ссылки

Источники

• Баше, CG (1612 г.). Приятные и восхитительные задачи, решаемые с помощью чисел (на французском языке).
• Грэм, РЛ; Кнут, Делавэр ; Паташник, О. (1989). Конкретная математика: основа информатики . Эддисон Уэсли. ISBN  978-0-201-14236-5 .
• Херштейн, Индиана; Капланский, И. (1974). Вопросы математические . Харпер и Роу. ISBN  9780060428037 .
• Иосиф Флавий (н. д.). Сочинения Иосифа Флавия: в трех томах; с иллюстрациями . Перевод Уильяма Уистона. Лондон: Джордж Рутледж и сыновья.
• Ньюман, младший (1988). Мир математики . Том. 4. Темпус.
• Пак, Чан Ву; Тейшейра, Рикардо (2018). «Серийное исполнение задачи Иосифа Флавия». Корейский Дж. Математика . 26 (1): 1–7. дои : 10.11568/kjm.2018.26.1.1 .
• Робинсон, WJ (1960). «Проблема Иосифа Флавия». Математика. Газ . 44 (347): 47–52. дои : 10.2307/3608532 . JSTOR   3608532 . S2CID   125735054 .
• Роуз Болл, WW (1905). Математические развлечения и очерки (2-е изд.). Лондон: Макмиллан.
• Забелл, С.Л. (1976). «Письмо в редакцию» (PDF) . Ежеквартальный журнал Фибоначчи . 14 : 48–51.

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

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Глава 14: Расширение структур данных». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. п. 318. ИСБН  0-262-03293-7 .
• Дауди, Джеймс; Мэйс, Майкл Э. (1989). «Перестановки Иосифа» . Журнал комбинаторной математики и комбинаторных вычислений . 6 : 125–130.
• Халбайзен, Л.; Хунгербюлер, Н. (1997). «Проблема Иосифа Флавия» . Дж. Теор. Номбрес Бордо . 9 (2): 303–318. дои : 10.5802/jtnb.204 .
• Якобчик, Ф. (1973). «Об обобщенной проблеме Иосифа Флавия» . Глазовская математика. Дж . 14 (2): 168–173. дои : 10.1017/S0017089500001919 . S2CID   122980022 .
• Ллойд, Эррол Л. (1983). «Алгоритм O (n logm) для проблемы Иосифа Флавия». Дж. Алгор . 4 (3): 262–270. дои : 10.1016/0196-6774(83)90025-1 .
• Одлизко, Андрей М.; Уилф, Герберт С. (1991). «Функциональная итерация и проблема Джозефуса» . Глазго Математика. Дж . 33 (2): 235–240. дои : 10.1017/S0017089500008272 . S2CID   123160551 .
• Раски, Фрэнк; Уильямс, Аарон (2010). «Проблема кошачьего Иосифа». Лект. Нет. Комп. Наука . Конспекты лекций по информатике. 6099 : 343–354. Бибкод : 2010LNCS.6099..343R . дои : 10.1007/978-3-642-13122-6_33 . ISBN  978-3-642-13121-9 . ВЕСЕЛО2010
• Раски, Фрэнк; Уильямс, Аарон (2012). «Проблема кошачьего Иосифа». Теория вычислений. Сист . 50 : 20–34. CiteSeerX   10.1.1.157.2956 . дои : 10.1007/s00224-011-9343-6 . S2CID   2273820 .
• Салливан, Шон; Инско, Эрик (2018). «Вариант проблемы кошачьего Иосифа». arXiv : 1803.11340 [ math.CO ].
• Терио, Николас (2001). «Обобщения проблемы Иосифа Флавия» Полезный. Математика. (58): 161–173. CiteSeerX   10.1.1.164.2015 .
• Вудхаус, Дэвид (1973). «Расширенная проблема Иосифа Флавия». Преподобный Мат. Хисп.-амер . 33 (4): 207–218.

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

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