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

Задача Йосипа Флавія на 9 перших натуральних чисел з довжиною кроку 5 (зелений позначає елемент, з якого починається відлік, червоний — елемент, який вилучається на поточному кроці)

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

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

Історія

Час рухається всередину по спіралі, зелені крапки позначають живих солдатів, сірі мертвих солдатів, а хрестики — вбивства. Солдати з номерами 16 та 31 залишаються останніми.

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

Однак у цій крайній скруті він не був позбавлений своєї звичайної кмітливості; але, довірившись Божому провидінню, він піддав своє життя небезпеці [наступним чином]: «А тепер, — сказав він, — оскільки між вами вирішено, що ви помрете, давайте віддамо нашу взаємну смерть на визначення жереба. Кому випаде жереб першим, нехай буде вбитий тим, кому випаде другий жереб, і таким чином фортуна пройде через усіх нас, і ніхто з нас не загине від власної руки, бо було б несправедливо, якби, коли решти не стане, хтось покаявся і врятувався». Ця пропозиція здалася їм дуже справедливою, і коли він переконав їх розв'язувати це питання жеребкуванням, то витягнув один із жеребків і для себе. Той, кому випав перший жереб, підставив шию тому, кому випав наступний, ніби припускаючи, що полководець помре серед них негайно, бо вони вважали, що смерть, якщо Йосиф помре з ними, солодша за життя; але він залишився з другим до останнього, чи то випадково так сталося, чи то з Божого промислу. Позаяк він дуже хотів не бути засудженим жеребом, ані, якби його залишили до останнього, не заплямувати свою правицю кров'ю своїх земляків, то вмовив його довірити йому свою вірність і жити так само добре, як і він сам.

— Йосип Флавій, Юдейська війна, Книга III, гл. 8, п. 7

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

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

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

Розв'язок

Нехай n — початкова кількість об'єктів у колі, а q — розмір кроку вибування, тобто q-1 об'єктів пропускається, а q-тий вибуває. Об'єкти в колі пронумеровані від 1 до n, лічба починається з 1-ї позиції. $J_{q}(n)$ — позиція об'єкта, який залишиться останнім, в початковому колі.

Випадок q = 2

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

Розглянемо ситуацію, коли в початковому колі знаходиться $2n$ об'єктів. Після першого проходження по колу зникнуть об'єкти з парними номерами, об'єкти, які залишаться, перемістяться з k-ої позиції на ${\frac {1}{2}}(k+1)$. В тому числі $J_{2}(2n)$ переміститься на позицію ${\frac {1}{2}}(J_{2}(2n)+1)$ і оскільки розмір нового кола дорівнює n, то номер цієї позиції також дорівнює $J_{2}(n).$ Звідси

$J_{2}(2n)=2J_{2}(n)-1$ при $n\geqslant 1.$

Якщо в початковому колі знаходиться $2n+1$ об'єктів, то після першого проходження по колу до першого об'єкта включно для того, щоб розмір нового кола став дорівнювавати n, зникнуть об'єкти з парними номерами та перший об'єкт, номери тих об'єктів, які залишаться, перемістяться з k-ої позиції на ${\frac {1}{2}}(k-1)$. Аналогічно до попередньої ситуації буде справедлива рівність

$J_{2}(2n+1)=2J_{2}(n)+1$ при $n\geqslant 1.$

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

$J(n)=2J(\lfloor n/2\rfloor )-(-1)^{n}.$

Для $n=1$ зрозуміло, що останнім залишиться об'єкт, з якого складається коло, тобто $J_{2}(1)=1.$

Якщо $n$ представити у формі $n=2^{m}+l,$ де $2^{m}$ — найбільший степінь двійки, що не перевищує $n,$ та $0\leqslant l<2^{m},$ то за допомогою математичної індукції можна показати, що

$J_{2}(2^{m}+l)=2l+1.$

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

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

Також можна довести, що $J_{2}(n)$ відповідає циклічному зсуву $n$ у бінарному вигляді на один розряд вліво. Тобто, якщо

$n=(1b_{m-1}b_{m-2}\dots b_{1}b_{0})_{2},$

то

$J_{2}(n)=(b_{m-1}b_{m-2}\dots b_{1}b_{0}1)_{2}.$

Випадок q = 3

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

$J_{3}(n)=\left(\left\lceil {\frac {3}{2}}J_{3}\left(\left\lfloor {\frac {2}{3}}n\right\rfloor \right)+a_{n}\right\rceil {\bmod {n}}\right)+1,$

де

$a_{n}={\begin{cases}-2,&\quad n\equiv 0{\bmod {3}}\\1,&\quad n\equiv 1{\bmod {3}}\\-0.5,&\quad n\equiv 2{\bmod {3}}\end{cases}}.$

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

$J_{3}(n)=3n+1-\left\lfloor K\left({\frac {3}{2}}\right)^{\lceil \log _{3/2}((2n+1)/K)\rceil }\right\rfloor ,$

де K = 1.62227050288476731595695098289932411…

Загальний випадок

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

$J_{q}(n)=\left((J_{q}(n-1)+q-1){\bmod {n}}\right)+1$ при $J_{q}(1)=1.$

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

$D:=1$;
поки $D\leqslant (q-1)n$ виконувати $D:=\left\lceil {\frac {q}{q-1}}D\right\rceil ;$
$J_{q}(n):=qn+1-D.$

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

Перестановка Йосипа

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

$J_{9,4}={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\4&8&3&9&6&5&7&2&1\end{pmatrix}}.$

За допомогою китайської теореми про остачі можна показати, що кількість всіх перестановок Йосипа на множині перших n натуральних чисел дорівнює L(n) = НСК(2, …, n).

Для двох перестановок Йосипа $J_{n,q_{1}}$ та $J_{n,q_{2}}$ виконується рівність $J_{n,q_{1}}(i)=J_{n,q_{2}}(i)$ для всіх $i=1,\dots ,t,$ де t — фіксоване натуральне число, не більше за n, тоді й лише тоді, коли $q_{1}\equiv q_{2}{\bmod {L}}(n,t),$ де L(n,t) = НСК(n+1-t, …, n-1, n).

При n = 1, 2, 3 перестановки Йосипа утворюють симетричну групу S_n, при n = 4, 5 — знакозмінну групу A_n, а при n > 5 ці перестановки групу не утворюють.

Варіації та узагальнення

Можна розглянути обернену задачу Йосипа Флавія, коли відомі n та k такі, що $1\leqslant k\leqslant n$ та J_q(n) = k, потрібно знайти розмір кроку q. Розв'язок цієї задачі завжди існує.

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

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

Застосування

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

Див. також

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

Література

• Томас Г. Кормен, Чарлз Е. Лейзерсон, Роналд Л. Рівест, Кліфорд Стайн. Вступ до алгоритмів. — Київ : К.І.С., 2019. — 1288 с. — ISBN 978-617-684-239-2.
• Josephus, Flavius (n.d.). The works of Flavius Josephus: in three volumes; with illustrations. Переклад: William Whiston. London: George Routledge & Sons.
• Graham, R. L.; Knuth, D. E.; Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (вид. 2). Addison Wesley. ISBN 0-201-55802-5.
• Herstein, I. N.; Kaplansky, I. (1974). Matters Mathematical. Harper and Row. ISBN 9780060428037.
• Hailperin, Max; Kaiser, Barbara; Knight, Karl (1999). Concrete abstractions: an introduction to computer science using Scheme. Max Hailperin. ISBN 978-0534952112.
• Newman, J. R. (1988). The World of Mathematics. Т. 4. Tempus.

Посилання

• Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every n^th out of 50 (maximum).
• Weisstein, Eric W. Josephus Problem(англ.) на сайті Wolfram MathWorld.