Задача Иосифа Флавия
Задача Иосифа Флавия (англ. Josephus problem, Josephus permutation, фр. Problème de Josèphe) — задача, заключающаяся в следующем: по кругу стоит 41 воин, начиная с первого воина они убивают каждого третьего.
Спрашивается, в каком месте нужно встать, чтобы остаться последним выжившим. В более общей формулировке участвует n воинов, которые считаются по кругу, и убивают каждого m-го[1].
Общие сведения[править]
В 1612 году французский математик Клод Гаспар Баше де Мезириак в сборнике Problem es Plaisants описал данную задачу. Сюжет задачи основан на истории, описанной Иосифом Флавием в своём историческом труде «Иудейская война», в которой сообщается, что Флавий со своим отрядом из 40 человек после падения Йодфата скрылся в пещере, но был обнаружен римлянами. Все в отряде, помимо Флавия, предпочли самоубийство сдаче в плен. Флавий пытался отклонить своих товарищей от самоубийства. Однако они обвиняли его в трусости и хотели убить своего командира. Флавий пишет:
 |
И в этом тяжёлом положении Иосифа не покинуло его благоразумие: в надежде на милость Божию он решил рискнуть своей жизнью и сказал: «Раз решено умереть, так давайте предоставим жребию решить, кто кого должен убивать. Тот, на кого падёт жребий, умрёт от рук ближайшего за ним, и таким образом мы все по очереди примем смерть один от другого и избегнем необходимости сами убивать себя; будет, конечно, несправедливо, если после того, как другие уже умрут, один раздумает и останется в живых». Этим предложением он вновь возвратил себе их доверие; уговорив других, он сам также участвовал с ними в жребии. Каждый, на которого пал жребий, по очереди добровольно дал себя заколоть другому, последовавшему за ним товарищу, так как вскоре за тем должен был умереть также и полководец, а смерть вместе с Иосифом казалась им лучше жизни. По счастливой ли случайности, а быть может по божественному предопределению, остался последним именно Иосиф ещё с одним. А так как он не хотел ни самому быть убитым по жребию, ни запятнать свои руки кровью соотечественника, то он убедил и последнего сдаться римлянам и сохранить себе жизнь. Иосиф Флавий. Иудейская война, книга 3, глава 8, 7 |  |
В задаче Баше солдаты не бросают жребий, а встают по кругу и убивают каждого третьего. В этом случае у Иосифа появляется возможность не полагаться на волю случая, а гарантировано спастись. Баше спрашивает, где нужно встать Иосифу и его товарищу, чтобы остаться последними, на кого выпадет жребий[2].
Обобщение этой задачи выглядит следующим образом. Предполагается, что каждый m-й человек будет казнён из группы численностью n, в которой p-й человек останется в живых. Если в круг добавить x человек, то оставшийся в живых будет находиться на p + mx-й позиции, если она меньше или равна n + x. Если x — наименьшее значение, при котором p + mx > n + x, то выживший находится на позиции (p + mx) − (n + x).
Практическое значение[править]
Задача Иосифа Флавия может использоваться для создания шифров, основанных на перестановке символов или элементов данных в определённом порядке, перемешивания символов в текстовом сообщении перед его передачей для повышения безопасности. Задача Иосифа Флавия может быть использована для моделирования различных дискретных процессов, таких как процессы эволюции популяции, банковские очереди или обработка данных в компьютерных системах. Она может помочь оптимизировать распределение ресурсов и времени для достижения оптимальных результатов. И т. д.[3]
Влияние[править]
Задача вдохновила Станислава Улама на создание понятия счастливого числа[2].
См. также[править]
Источники[править]
- ↑ https://habr.com/ru/articles/709540/?ysclid=mji8mrzyr4764020490
- ↑ 2,0 2,1 Dowdy, James; Mays, Michael E. Josephus permutationsангл. // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1989. — том 6. — С. 125—130.
- ↑ https://libeldoc.bsuir.by/bitstream/123456789/57104/1/YUrkevich_O_zadache.pdf
