Задача Йосипа Флавія

Задача Йосипа Флавія — задача в комбінаториці, пов'язана з грою в лічилку.

У загальному вигляді задача виглядає наступним чином: на колі було розміщено задану кількість об'єктів, а потім рухаючись по колу в одному напрямку, пропускаючи фіксоване число об'єктів, вилучали по об'єкту поки не залишився лише один. Потрібно знайти об'єкт, який залишився.

Історія

Задача названа на честь Йосипа Флавія, римського історика єврейського походження, який жив у I ст. н. е. Згідно з безпосередніми свідченнями Йосипа про , він, бувши командиром, разом зі своїми 40 воїнами були заблоковані в печері римськими солдатами. Більшість з них не хотіли здаватися, тому вони домовились, що будуть убивати один одного шляхом жеребкування, а той хто залишиться в живих останнім мусить сам себе вбити. І як потім писав сам Йосип Флавій, що завдяки везінню, а можливо, і Божому промислу, він і ще один чоловік залишилися до кінця і, замість того, щоб вбити себе здалися римлянам. Ця історія описана в його книзі «Юдейська війна» (автор пише від третьої особи):

Залишається неясним порядок, в якому вони один одного вбивали. У 1612 році запропонував конкретний алгоритм, який полягав у тому, щоб поставити солдат у коло і рахувати по три, щоб визначити порядок вбивства. Конкретні деталі цієї історії суттєво відрізняються в різних джерелах. Наприклад, у та (1974) Йосип і його 39 побратимів стоять у колі, а кожного сьомого вбивають.

Хоч Йосип у своїй книзі стверджував, що це трапилося випадково, але збережений його слов'янський рукопис розповідає іншу історію: він хитро вирахував, де йому потрібно стати, і обдурив інших. Також стверджується, що другий вцілілий воїн був його спільником; тож задача полягала в тому, щоб знайти такі місця для двох, щоб вони залишилися останніми в живих. Він розмістив себе і другого чоловіка на 31-му і 16-му місці відповідно.

У середньовіччі була придумана інша версія цієї задачі, у якій 15 турків і 15 християн знаходяться на борту корабля під час шторму. Корабель потоне, якщо половина пасажирів не буде викинута за борт. Всі 30 стають у коло, і кожну дев'яту людину кидають у море. Потрібно визначити, де потрібно стояти християнам, щоб тільки турки були викинуті. В інших версіях ролі турків і християн міняються місцями.

Розв'язок Нехай  — початкова кількість об'єктів у колі, а  — розмір кроку вибування, тобто об'єктів пропускається, а -тий вибуває. Об'єкти в колі пронумеровані від до , лічба починається з -ї позиції.  — позиція об'єкта, який залишиться останнім, в початковому колі.

Випадок q = 2 У цьому випадку задачу можна розв'язати явно.

Розглянемо ситуацію, коли в початковому колі знаходиться об'єктів. Після першого проходження по колу зникнуть об'єкти з парними номерами, об'єкти, які залишаться, перемістяться з -ої позиції на . В тому числі переміститься на позицію і оскільки розмір нового кола дорівнює , то номер цієї позиції також дорівнює Звідси при

Якщо в початковому колі знаходиться об'єктів, то після першого проходження по колу до першого об'єкта включно для того, щоб розмір нового кола став дорівнювавати , зникнуть об'єкти з парними номерами та перший об'єкт, номери тих об'єктів, які залишаться, перемістяться з -ої позиції на . Аналогічно до попередньої ситуації буде справедлива рівність при

Отримані формули можна звести до однієї:

Для зрозуміло, що останнім залишиться об'єкт, з якого складається коло, тобто

Якщо представити у формі де  — найбільший степінь двійки, що не перевищує та то за допомогою математичної індукції можна показати, що

Цю формулу можна переписати так, щоб вона залежала лише від :

Також можна довести, що відповідає циклічному зсуву  у бінарному вигляді на один розряд вліво. Тобто, якщо

то

Випадок q = 3 Аналогічно до попереднього випадку можна вивести наступну рекурентну формулу:

де

Для цього випадку також можна вивести явну формулу:

де

Загальний випадок У 1899 математик Пітер Тейт запропонував рекурсивний алгоритм, який пов'язує номер об'єкта, який залишиться останнім, на певному кроці з його номером на наступному кроці: при

Більш швидший алгоритм розробив Дональд Кнут:

поки виконувати

Також для розв'язання цієї задачі існують алгоритми, які використовують масиви, кільцеві списки або бінарні дерева.

Перестановка Йосипа Перестановка перших  натуральних чисел , утворена шляхом застосування процедури вилучення із задачі Йосипа Флавія з довжиною кроку , називається перестановкою Йосипа. Наприклад,

За допомогою китайської теореми про остачі можна показати, що кількість всіх перестановок Йосипа на множині перших  натуральних чисел дорівнює 

Для двох перестановок Йосипа та виконується рівність для всіх де  — фіксоване натуральне число, не більше за , тоді й лише тоді, коли де 

При перестановки Йосипа утворюють симетричну групу , при  — знакозмінну групу , а при  ці перестановки групу не утворюють.

Варіації та узагальнення Можна розглянути обернену задачу Йосипа Флавія, коли відомі та такі, що та потрібно знайти розмір кроку . Розв'язок цієї задачі завжди існує.

Задача, у якій об'єкти додатково мають по «життів», тобто об'єкт вибуває тоді, коли його виберуть разів, називається котячою задачею Йосипа Флавія. При фіксованих та об'єкт, який залишиться останнім, буде незмінним при всіх , не менших за -ге число Фібоначчі. Також можна розглянути задачу, де об'єкти мають по різній кількості «життів».

Крім цього, початкову задачу можна узагальнити так, щоб на кожному кроці вилучали по  об'єктів.

Застосування Для шифрування зображень були запропоновані методи на основі хаотичних систем, які для процесу плутанини використовують перестановки Йосипа.

Див. також Щасливе число (lucky number) Динамічне програмування

Примітки

Література

Посилання Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every nth out of 50 (maximum).