Проблема Иосифа

В информатике и математике , то проблема Флавия (или Флавий перестановка ) теоретическая проблема , связанная с определенной считалкой .

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

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

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

История [ править ]

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

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

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

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

Варианты и обобщения [ править ]

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

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

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

Решение [ править ]

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

k = 2 [ редактировать ]

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

Если начальное количество людей было четным, то человек, занимавший позицию во второй раз по кругу, был изначально на месте (для каждого выбора ). Пусть . Человек, который теперь выживет, изначально занимал позицию . Это дает нам повторение${\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\;.}$

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

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

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

Самая элегантная форма ответа включает двоичное представление размера : может быть получено однобитным циклическим сдвигом влево самого себя. Если мы представим в двоичном формате как , то решение будет иметь вид . Доказательство этого следует из представления as или из приведенного выше выражения для .${\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}}$

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

п = 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  * / public  int  getSafePosition ( int  n )  { // найти значение L для уравнения int  valueOfL  =  n  -  Целое число . highOneBit ( n ); int  safePosition  =  2  *  значениеOfL  +  1 ;return  safePosition ; }

Побитовое [ править ]

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

п = 1 0 1 0 0 1

п = 0 1 0 0 1 1

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

Общий случай [ править ]

Динамическое программирование используется для решения этой проблемы в общем случае, выполняя первый шаг, а затем используя решение оставшейся проблемы. Когда индекс начинается с единицы, тогда человек, находящийся на смене от первого, занимает позицию , где 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\\\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}}}$

Примечания [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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