Считалка Иосифа Флавия: кого убить первым

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

(Во время написания поста погибло дофига нарисованных солдатиков).

«Я был в старшей школе, когда профессор Фил сказал мне решить эту задачу.
Он предложил решить ее вручную, на бумаге. Взять разное количество людей и найти закономерность, где n — количество мест, а w(n) место победителя.»

Рассмотрим, что произойдет на примере семи человек: 1 убивает 2. 3 убивает 4, 5 убивает 6. Ну, а для 7 нет 8, поэтому 7 убивает 1. Затем 3 убивает 5, 7 убивает 3. 7 победил.

Это Иосиф, он хочет жить.

У Иосифа в отряде был 41 человек. И вот это уже серьезно.

Рассмотрим пример, когда в группе 5 человек. 1 убивает 2, 3 убивает 4, 5 убивает 1, 3 убивает 5. Победителем становится 3.

Для шестерых. 1 убивает 2, 3 убиваетс4, 5 убивает 6, 1 убивает 3 и 5 убивает 1. Победитель — 5.

Появляются странные закономерности. Пока что победитель — это нечетное число.

Попал на четное место — кранты.

А теперь полностью заполним таблицу.

Возьмем одного человека. Что ж. Этот человек победил, так что это было легко.

Если есть два человека: 1 убивает 2. 1 — победитель.

Если есть три человека: 1 убивает 2, 3 убивает 1. 3 выиграл.

Если есть четыре человека: 1 убивает 2, 3 убивает 4, 1 убивает 3.

Если есть восемь человек: 1 убивает 2, 3 убивает 4, 5 убивает 6, 7 убивает 8, 1 убивает 3, 5 убивает 7, 1 убивает 5. Победителем становится 1.

Хорошо, результаты таковы: 1, 1, 3, 1, 3, 5, 7, 9.
Результат все время увеличивается на 2, но затем он сбрасывается в какой-то момент.

Сделаем быстро к 13, получим 11, а у 14 будет 13.

Теперь посмотрим, когда случится сброс до одного. Обратим внимание на числа, которые дают вам единицу. Уже можно догадаться, что у 16 победителем будет 1.

Сделаем вывод:
Если n (количество человек) — это 2 в степени, то выигрышное место — номер один.

Теперь я нарисую схему побольше. Схема на 16 человек.
После первого круга убийств останется вдвое меньше человек, то есть 8. Теперь опять начнем с первого. Проходимся по кругу, и снова вдвое меньше, то есть 4. Делаем еще один круг. Осталось два человека.Начинаем с номера один, и он побеждает.

А теперь рассмотрим, что происходит с числами, между 4 и 8.

Результат увеличивается на два. Но, когда я к 7 добавляю 2, то получается 9. Вот здесь и случится сброс до 1. И теперь я могу сказать, что, любую комбинацию можно расписать как 2 в степени плюс еще какое-то число.

Возьмем число 77. Самая большое число, из которого я могу извлечь корень — это 64. Тогда получим сумму: 64 + 13.

Затем распишем по такой же схеме для числа 13 самые большие корни: 8 + 4 + 1. Получается сумма двоек в степенях. 77=2⁶+2³+2²+2⁰. Ключевой момент в том, что степени не повторяются, значит мы все сделали правильно.

А теперь выведем формулу, где 64(n) — это 2 в степени А + 13 — это L, получится n=2ͣ+l

13 мы распишем, как сумму: 8+4+1 и подставим формулу n=2ͣ+l (13=8+5)
И нечетное число является количеством ходов, после которого нужно остановиться.
Я сделаю пять шагов. Итак: 1 убивает 2, 3 убивает 4, 5 убивает 6, 7 убивает 8, 9 убивает 10. Я остановился на номере 11. Теперь смотрите, что происходит: сколько людей осталось? То, что осталось — это и есть корень из двух. И как мы знаем, тот, кто победит в корне из двух — это тот, кто начнет!

Теперь смотрим: 11 убивает 12, 13 убивает 1, 3 убивает 5, 7 убивает 9. Снова возвращаемся к одиннадцатому, теперь осталось всего четыре человека. 11 убивает 13, 3 убивает 7.Осталось 2 человека и одиннадцатый начинает. 11-й победил.

Теория заключается в том, чтобы расписать число по формуле, где L меньше, чем 2 в степени a. А выигрышное место — это 2L+1.
У нас последняя сумма была 13=8+5, где 5 было L. Подставим в формулу и увидим, что все сходится: 2*5+1=11

Вернемся к нашей задаче. Там был 41 человек в отряде. 41=32+9
Возьмем нашу формулу 2L+1. Получим 19

Рисуем круг.
Итак, 1 убивает 2…
Мы теряем наши четные цифры.
41 убивает 1, 3 убивает 5...19 убивает 35, 35 убивает 1 и 19 убивает 35.

Формулу, что я написал, можно расписать в двоичном коде.Напишем сумму степеней: 41=2⁵+ 2³+2⁰. Код представляет собой ни что иное как двойки в степени. А код — это единица или ноль. Запишем по порядку двойки в степени слева самая большая в конце два в степени 0. Там, где степень соответствует нашему значению, то ставим 1, в ином случае — 0. Таким образом получаем: 2⁵ 2⁴ 2³ 2² 2¹ 2⁰. Двоичный код будет: 2⁵ — это 1, 2⁴ — это 0 и т.д… И получаем: 101001.

А сейчас покажу основную фишку в решении задачи. Выигрышная позиция будет вашим двоичным кодом, но первую цифру нужно перенести назад: 010011. Получается: 2⁰+2¹+(я пропустил 2² и 2³)+2⁴. А вот и сумма: 16+2+1, где ответ 19.

Вот и все решение для нашей задачи.

P.S.

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

Читать еще

• Josephus Problem на сайте Вольфрама ^[3]
• Видеолекция профессора Steven Skiena ^[4]
• Josephus problem на Википедии ^[5]

О школе GoTo

• Конкурс GoTo Algorithms Challenge Spring 2018 ^[6] (до 21 марта)
• Весенняя школа GoTo 2018 ^[7] (25-31 марта)
• Группа в ВК ^[8]
• Подписаться на рассылку ^[9]

Автор: MagisterLudi

Источник ^[10]