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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Задача виникла на основі легенди. Йосип Флавій був римським істориком, євреєм за походженням. Дія легенди відбувалася під час Першої іудейської війни. Легіон із 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.
Використано рішення Анатолія Казмерчука.

Посилання[ред.ред. код]