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

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

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

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

Історія

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

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

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

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

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

Розв'язок

Нехай Шаблон:Mvar — початкова кількість об'єктів у колі, а Шаблон:Mvar — розмір кроку вибування, тобто Шаблон:Math об'єктів пропускається, а Шаблон:Mvar-тий вибуває. Об'єкти в колі пронумеровані від Шаблон:Mvar до Шаблон:Mvar, лічба починається з Шаблон:Mvar-ї позиції. $J_q(n)$ — позиція об'єкта, який залишиться останнім, в початковому колі.

Випадок q = 2

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

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

$J_2(2n)=2J_2(n)-1$ при $n⩾1.$

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

$J_2(2n+1)=2J_2(n)+1$ при $n⩾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⩽l<2^m,$ то за допомогою математичної індукції можна показати, що

$J_2(2^m+l)=2l+1.$

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

$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(\lceil \frac{3}{2}{J}_3\left(\lfloor \frac{2}{3}n\rfloor \right)+a_n\rceil modn\right)+1,$

де

$a_n=\{\begin{array}{cc}-2,& n\equiv 0mod3\\ 1,& n\equiv 1mod3\\ -0.5,& n\equiv 2mod3\end{array}.$

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

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

де Шаблон:Math

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

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

$J_q(n)=((J_q(n-1)+q-1)modn)+1$ при $J_q(1)=1.$

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

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

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

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

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

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

Для двох перестановок Йосипа $J_{n,q_1}$ та $J_{n,q_2}$ виконується рівність $J_{n,q_1}(i)=J_{n,q_2}(i)$ для всіх $i=1,\dots ,t,$ де Шаблон:Mvar — фіксоване натуральне число, не більше за Шаблон:Mvar, тоді й лише тоді, коли $q_1\equiv q_{2}modL(n,t),$ де Шаблон:Math

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

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

Можна розглянути обернену задачу Йосипа Флавія, коли відомі Шаблон:Mvar та Шаблон:Mvar такі, що $1⩽k⩽n$ та Шаблон:Math потрібно знайти розмір кроку Шаблон:Mvar. Розв'язок цієї задачі завжди існує.

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

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

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

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

Див. також

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

Література

• Шаблон:Книга
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book

Посилання

• Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every n^th out of 50 (maximum).
• Шаблон:MathWorld