Проблема Иосифа - Josephus problem - Wikipedia

В Информатика и математика, то Проблема Иосифа (или же Перестановка Иосифа) - теоретическая проблема, относящаяся к определенному счетная игра.

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

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

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

История

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

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

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

У Иосифа был сообщник; тогда проблема заключалась в том, чтобы найти места двух последних оставшихся в живых (чей заговор обеспечил их выживание). Утверждается, что он поставил себя и другого мужчину на 31-е и 16-е места соответственно.^[7]

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

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

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

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

Решение

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

k = 2

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

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

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

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

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

Когда мы заносим в таблицу значения ${\displaystyle n}$ и ${\displaystyle f(n)}$ мы видим узор: OEIS: A006257

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

Это говорит о том, что ${\displaystyle f(n)}$ - возрастающая нечетная последовательность, которая перезапускается с ${\displaystyle f(n)=1}$ всякий раз, когда индекс п степень 2, поэтому, если мы выберем м и л так что ${\displaystyle n=2^{m}+l}$ и ${\displaystyle 0\leq l<2^{m}}$, тогда ${\displaystyle f(n)=2\cdot l+1}$.Ясно, что значения в таблице удовлетворяют этому уравнению. Или мы можем думать, что после ${\displaystyle l}$ люди мертвы есть только ${\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}$.

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

Если ${\displaystyle 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}$, где второе равенство следует из предположения индукции.

Если ${\displaystyle 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}$, где второе равенство следует из предположения индукции. Это завершает доказательство.

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

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

Самая элегантная форма ответа включает двоичное представление размера ${\displaystyle n}$: ${\displaystyle f(n)}$ может быть получен однобитным циклическим сдвигом влево ${\displaystyle n}$ сам. Если мы представляем ${\displaystyle 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 n}$ в качестве ${\displaystyle 2^{m}+l}$ или из приведенного выше выражения для ${\displaystyle f(n)}$.

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

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

п = 1 0 1 0 0 1

2^м = 1 0 0 0 0 0

л = 0 1 0 0 1

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

Побитовое

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

п = 1 0 1 0 0 1

п = 0 1 0 0 1 1

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

k = 3

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

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

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

${\displaystyle f(n)=3(n-round(\alpha \cdot (3/2)^{m}))+2}$ если бы мы собрали еще ${\displaystyle 1}$

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

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

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

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

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

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

Мы можем убедиться в этом, глядя на каждый последующий проход чисел ${\displaystyle 1}$ через ${\displaystyle 41}$:

${\displaystyle 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}$

${\displaystyle 2,4,7,8,11,13,16,17,20,22,25,26,29,31,34,35,38,40}$

${\displaystyle 2,4,8,11,16,17,22,25,29,31,35,38}$

${\displaystyle 2,4,11,16,22,25,31,35}$

${\displaystyle 2,4,16,22,31,35}$

${\displaystyle 4,16,31,35}$

${\displaystyle 16,31}$

${\displaystyle 31}$

Общий случай

Динамическое программирование используется для решения этой проблемы в общем случае, выполняя первый шаг, а затем используя решение оставшейся проблемы. Когда индекс начинается с единицы, то человек в ${\displaystyle s}$ смены от первого лица на позиции ${\displaystyle ((s-1){\bmod {n}})+1}$, где n - общее количество человек. Позволять ${\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}$ дает повторение^[12]

${\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}$ вместо.

Этот подход имеет Продолжительность ${\displaystyle O(n)}$, но для маленьких ${\displaystyle k}$ и большой ${\displaystyle n}$ есть другой подход. Второй подход также использует динамическое программирование, но имеет время выполнения. ${\displaystyle O(k\log n)}$. Он основан на рассмотрении убийства k-й, 2k-й, ..., ${\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\\\left\lfloor {\frac {k((g(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{where }}n'=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\\end{cases}}}$

Примечания

1. Проблема Иосифа. Решение задачи Проблема Иосифа в Код Розетты, написано на языке Frmulæ. Вики Сообщества. Проверено 19 сентября 2019 года.
2. Флавий Иосиф, Войны евреев III. 8. 7. (Перевод Уильяма Уистона).
3. Дауди и Мэйс 1989, п. 125
4. Баше, К. Г. (1612). Problemes Plaisants ed Delectables qui se font par les Nombres. п. 174.
5. Herstein, I. N .; Капланский, И. (1974). Вопросы математические. Харпер и Роу. стр.121–126.
6. Забелл, С. Л. (1976). "Письмо редактору". Ежеквартальный отчет Фибоначчи. 14: 48, 51.
7. Роуз Болл, У. У. (1896). Математические развлечения и эссе (2-е изд.). Макмиллан.
8. Ньюман, Дж. Р. (1988). Мир математики. 4. Темпус. С. 2403–2405.
9. Graham, R.L .; Кнут, Д. Э.; Паташник, О. (1989). Конкретная математика: основа компьютерных наук. Эддисон Уэсли. п. 8. ISBN  978-0-201-14236-5.
10. Робинсон, У. Дж. (1960). «Проблема Иосифа». Математический вестник. 44 (347): 47–52. Дои:10.2307/3608532. JSTOR  3608532.
11. «Проблема Иосифа с использованием побитовой операции (Java)». GitHub. 7 января 2018 г.. Получено 7 января, 2018.
12. Пак, Чан Ву; Тейшейра, Рикардо (2018). «Серийная казнь Иосифа Проблема». Корейский J. Math. 26 (1): 1–7. Дои:10.11568 / kjm.2018.26.1.1.

Рекомендации

• Робинсон, У. Дж. (1960). «Проблема Иосифа Флавия». Математика. Вестник. 44 (347): 47–52. Дои:10.2307/3608532. JSTOR  3608532.
• Вудхаус, Дэвид (1973). «Расширенная проблема Иосифа Флавия». Преподобный Мат. Hisp.-Amer. 33 (4): 207–218.
• Якобчик, Ф. (1973). «Об обобщенной проблеме Иосифа Флавия». Glasow Math. J. 14 (2): 168–173. Дои:10.1017 / S0017089500001919.
• Ллойд, Эррол Л. (1983). «Алгоритм O (n logm) для проблемы Иосифа Флавия». Дж. Алгор. 4 (3): 262–270. Дои:10.1016/0196-6774(83)90025-1.
• Дауди, Джеймс; Мэйс, Майкл Э. (1989). «Перестановки Иосифа Флавия». Журнал комбинаторной математики и комбинаторных вычислений. 6: 125–130.
• Одлызко, Андрей М .; Уилф, Герберт С. (1991). «Функциональная итерация и проблема Иосифа Флавия». Glasgow Math. J. 33 (2): 235–240. Дои:10.1017 / S0017089500008272.
• Halbeisen, L .; Hungerbühler, Н. (1997). "Проблема Иосифа". J. Théor. Номбр Бордо. 9 (2): 303–318. Дои:10.5802 / jtnb.204.
• Терио, Николя (2001). «Обобщение проблемы Иосифа Флавия». Util. Математика. (58): 161–173. CiteSeer^Икс: 10.1.1.164.2015
• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). «Глава 14: Расширение структур данных». Введение в алгоритмы (Второе изд.). MIT Press и McGraw-Hill. п. 318. ISBN  0-262-03293-7.
• Шамс-Барах, Армин (2002). «Формулировка расширенной проблемы Иосифа Флавия» (PDF).
• Раски, Фрэнк; Уильямс, Аарон (2010). «Проблема кошачьего Иосифа». Lect. Нет. Комп. Наука. Конспект лекций по информатике. 6099: 343–354. Bibcode:2010LNCS.6099..343R. Дои:10.1007/978-3-642-13122-6_33. ISBN  978-3-642-13121-9. FUN2010
• Раски, Фрэнк; Уильямс, Аарон (2012). "Проблема кошачьего Иосифа". Теория вычисл. Системы. 50: 20–34. Дои:10.1007 / s00224-011-9343-6. S2CID  2273820.
• Салливан, Шон; Инско, Эрик (2018). «Вариант проблемы Кошачьего Иосифа». arXiv:1803.11340 [math.CO ].

внешняя ссылка

• Армин Шамс-Барах Формулировка расширенной проблемы Иосифа Флавия
• Хальбайзен, Лоренц Дж. "Проблема Иосифа" (PDF).
• Игра Иосифа Флавия (Java-апплет) в завязать узел разрешая выбор каждого n^th из 50 (максимум).
• Вайсштейн, Эрик В. "Проблема Иосифа". MathWorld.
• "Проблема Иосифа Флавия - Numberphile" на YouTube