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

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

Задача ночит имя Иосифа Флавия — известного историка I века. Существует легенда, что Иосиф выжил и стал известным благодаря своему математическому дару. В ходе иудейской войны он, будучи в составе отряда из 41 иудейского война был загнан римлянами в пещеру. Отряд, в котором состоял Иосиф, обладал неимоверно сильным боевым духом и не желая сдаваться в плен, войны предпочли самоубийство. Они встали в круг и последовательно начали убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Иосиф же не разделял чаяний сослуживцев. Чтобы не быть убитым, Иосиф вычислил "спасительные места" на которое поставил себя и своего товарища.

... и лишь поэтому мы знаем его историю

Анализ задачи

Давайте обобщим задачу и высторим n человек в круг, пронумеровав каждого от 1 до n. Затем мы будем исключать каждого второго из круга до тех пор, пока не уцелеет только один человек.

Давайте рассмотрим процесс исключения при n=10:

2 4 6 8 10 3 7 1 9
Следовательно выживет человек с номером 5.

Давайте зададим функцию J(n), где n — кол-во человек в круге, а J(n) — "спасительное место". Для дальнейшего анализа потребуется составить таблицу для n=1..6 (от 1 до 6)

n 1 2 3 4 5 6
J(n) 1 1 3 1 3 5

Если изначально имеется 2n людей, то после первого прохода по кругу мы останемся с номерами {1,3,5,7,...,2n-3,2n-1} и следующий проход будет начинаться уже с номера 3.

J(2n)=newNo(J(n));//где newNo(k)=2k-1

Таким образом очень легко перейти к рекурентной формуле:

J(2n)=2J(n)-1, n>0
Тогда вычислить J(20)=2*J(10)-1=2*5-1=9 не составляет труда.

Вообще говоря, можно говорить о том, что J(5*2^m)=2^(m+1)+1

Нечетный случай

Теперь давайте вернемся к нечетному случаю. Чудесным образом оказывается, что в случае 2n+1 людей жертва с номером 1 уничтожается сразу после жертвы с номером 2n, таким образом выживают следующие номера:

Мы получили почти изначальную ситуацию с n людьми, но на этот раз номера уцелевших удваиваются и увеличиваются на 1. Получается J(2n+1)=2*J(n)+1, n>0. Давайте перейдем к рекурентной формуле:

J(1) = 1
J(2n) = 2*J(n) - 1, n>0
J(2n+1) = 2*J(n) + 1, n>0

Ура! Мы получили замечательное соотношение, которое позволяет получать результат гораздо быстрее, чем при формуле J(n) из J(n-1). Для тех кто в танке: счетчик уменьшается сразу в 2 раза! Таким образом можно вычислить J(10^6) только за 19 раз! Результат несомненно радует, однако, надеюсь у вас все еще сохранилось желание найти J(n) в замкнутой форме.

Новая формула позволяет быстро составить таблицу для первых 16ти значений (все зависит от вашего терпения).

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Эврика! Мы нашли закономерность. Теперь настало время осознать саму закономерность. Нетрудно заметить (отличная фраза), что если сгруппировать значения n по степеням 2, то в каждой группе J(n) всегда будет начинаться с 1, а затем увилчиваться на 2. Таким образом, если записать n в виде n=2^m+k, где 2^m - наибольшая степень 2, но не большая n, а k - "остаток" от рекуррентного соотношения, получается:

J(2^m+k)=2k+1, m ∈ [0,+∞] и k ∈ [0,2^m]

Осталось доказать эту формулу. А доказывать мы будем по индукции (ММИ) по m. При m=0 k=0, база индукции J(1)=1 предельно очевидна. Индукционный шаг будет зависить от ситуации чет/нечет k. Если m>0 и 2^m + k = 2n, то k четно и получаем

J(2^m+k)=2J(2^(m-1)+k/2)-1=2(2k/2+1)-1=2k+1
(Аналогично доказывается нечетный случай, когда 2^m+k=2n+1. Кстати, из рекуррентой формулы можно получить следующее соотношение J(2n+1)-J(2n)=2. Индукция выполнена, справедливость установлена.

Степень двойки

В процессе решения большую роль играла двойка. Соответственно следует обратиться к двоичному представлению n и J(n). Пусть двоичные разложения величин n имеют вид

n = {bm bm-1 .. b1 b0}
n = bm2^m + bm-12^(m-1) + ... + b12+b0
где bi равно либо 1, либо 0, старший бит bm равен 1. Из соотношения n=2^m + k получаем
n = {1bm-1 bm-2 ... b1b0}2
k = {0bm-1bm-2 ... b1 b0}2
...
J(n) = {bm-1 bm-2 ... b1 b0 bm}2

=>

J({bm bm-1 ... b1 b0}2) = {bm-1 bm-2 ... b1 b0 bm}2
Видно, что мы получили J(n) путем циклического сдвига двоичного представления n влево на один бит. Если мы начнем с n и итерируем функцию J m+1 раз, то осуществим циклический сдвиг на m+1 битов.

Disclaimer: полностью уйти от рекурентности нам так и не удастся, однако мы сможем значительно обобщить случай до любого "основания". То есть получить формулу общую формулу, но все же рекурентную. Дальнейшие рассуждения занимают примерно 3 страницы A4. Любознательный читатель может открыть книгу товарища Роналда Грэхема (Ronald Graham) под названием "Конкретная математика" (Concrete Mathematics) на странице 29 и дочитать эту увлектельную историю.

Случай m = 2

Хотя для m=2 рекуррентную формулу все же можно получить

"Вычислительное решение"

Java

int josephus(int n, int k) {
       return josephus(n, k, 1);
 }
 int josephus(int n, int k, int startingPoint) {
     if(n == 1)
         return 1;
     int newSp = (startingPoint + k - 2) % n + 1;
 
     int survivor = josephus(n - 1, k, newSp);
     if (survivor < newSp) {
         return survivor;
     } else
         return survivor + 1;
 }

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 29.05.17)