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

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

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

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

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

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

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

При $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$ .