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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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. Зазначимо, що у випадку ${\displaystyle m=n}$ відповіддю буде ${\displaystyle k=1}$.

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

Див. також

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

Література

• М. А. Алексеев. Задача Иосифа Флавия // Империя Математики. — 2001. — № 2. — С. 22—28.
• Дональд Кнут, Роналд Грэхем, ^[ru]. ^[en] = Concrete Mathematics. A Foundation for Computer Science. — М. : Мир; , 2006. — С. 703. — .

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

• 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

Примітки

1. . www.vehi.net. Архів оригіналу за 20 серпня 2020. Процитовано 21 січня 2022.
2. . Хабр (рос.). Архів оригіналу за 21 січня 2022. Процитовано 21 січня 2022.
3. Казмерчук Анатолій Іванович