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

Задача Йосипа Флавія (проблема Йосипа Флавія) — математична задача.

Опис задачі і розв'язок

Історія задачі

Задача виникла на основі легенди. Йосип Флавій був римським істориком, євреєм за походженням. Дія легенди відбувалася під час Першої юдейської війни. Гарнізон із 41 сикарія, що обороняв галілейський замок Масада, не хотів здаватись в полон римлянам. Сикарії стали в коло й домовились, що кожні два воїни будуть убивати третього, доки не загинуть всі. Самогубство — тяжкий гріх, але той, хто врешті-решт залишиться останнім, мусить це зробити. Йосип Флавій, командир цього гарнізону, нібито розрахував, де йому та його другу потрібно стати, щоб залишитись останніми, але не для того щоб убити друга, а щоб здати замок римлянам.

Сучасне формулювання задачі

У сучасному формулюванні задачі беруть участь $\ n$ воїнів і вони вбивають кожного $\ m$. Слід знайти номер $\ k$ початкової позиції воїна, який повинен залишитись останнім.

При $n=1,..,m$. Нехай $n>m$. Після закреслювання чисел з $2$ до $m$ залишається $n-m+1$, при чому на першому місці стоїть число $m+1$, на другому — $m+2$ і т. д. На місці з номером $n-m$ стоїть число $n$. І нарешті, на місці з номером $n-m+1$ стоїть число $1$. Тому справедлива рекурентна формула:

$k(n,m)=k(n-m+1,m)$, якщо $k(n-m+1,m)<n-m+1$, i

$k(n,m)=1$, якщо $k(n-m+1,m)=n-m+1$.

Із формули видно, що, якщо $k(n,m)=q$, i при $n>q$ то $k(n+m-1,m)=q+m$

Тому, для $r=1,...,m-1$ маємо:

$k(s(m-1)+r,m)=sm+1$, якщо $sm<s(m-1)+r$, то є при $s<r$, а при $s=r$ маємо: $k(rm,m)=1$. Потім $k(s(r-1)+rm,m)=sm+1$, якщо $sm<s(m-1)+rm$, то є при $s<rm$, а при $s=rm$ маємо $k(rm^{2},m)=1$. І т.д. У загальному випадку для $l=0,1,2,...$

$k(s(m-1)+rk^{l},m)=sm+1$, якщо $sm<s(m-1)+rm^{l}$, то є при $s<rm^{l}$, а при $s=rm^{l}$ маємо $k(rm^{l+1},m)=1$

Виведемо загальну формулу для $k(n,m)$ при $m>1$. Виразимо число $n=s(m-1)+rm^{l}$, де $r=1,...m-1,l=0,1,2,..,s=0,...,rm^{k-1}$ Число $r$ дає такий же залишок при ділені на $q-1$, як і $n$.

Тому $r=(n-1)mod(m-1)+1$, і, $l=log_{m}(n/r)$, $s=(n-rm^{l})/(m-1)$.

Після підстановки отримаємо основну формулу:

$k(n,m)={\frac {m}{m-1}}(n-((n-1)\mod {(m-1)}+1)m^{{\mathcal {b}}\log _{m}{{\frac {n}{(n-1)\mod {(m-1)+1}}}{\mathcal {c}}}})+1$

Формула працює лише для випадків, коли m не дорівнює n. Зазначимо, що у випадку $m=n$ відповіддю буде $k=1$.

Використано розв'язання Анатолія Казмерчука.

Див. також

• Щасливе число (lucky number)

Література

• М. А. Алексеев. Задача Иосифа Флавия // Империя Математики. — 2001. — № 2. — С. 22—28.
• Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М. : Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7.

Інтернет-ресурси

• 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.
• The Josephus Problem - Numberphile на YouTube
• Generalized Josephus Problem