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

В современном варианте эта задача формулируется следующим образом. Выстроим в круг n человек и будем исключать каждого второго из оставшихся до тех пор пока не останется один человек. Если в круг было выстроено n человек, то обозначим номер уцелевшего I(n).

Рассмотрим пример n=10.

Порядок исключение следующий: 2, 4, 6, 8, 10, 3, 7, 1, 9. Оставшийся номер I(10)=5.

Можно рассмотреть ряд простых примеров, для которых легко получаются следующие результаты:

Для того, чтобы наметить подходы к решению нашей задачи рассмотрим две ситуации. Первый случай, когда число людей чётное 2n.

После того как убирается номер 2n, новый проход начинается с номера 3. Будем рассматривать второй проход как новую задачу, но число в этой задаче равно n. Можно определить новую нумерацию для задачи с числом n. Как связаны номера старой нумерации . Нетрудно понять, что имеет место связь . Поэтому имеет место равенство

Опять осталось n человек. Ответ на вопрос, как связаны номера в старой нумерации с номерами в новой нумерации следующий . Поэтому имеет место следующая формула

.

Мы стремимся получить выражение для в замкнутой форме. Составим таблицу первых значений .

Из этой таблицы можно легко увидеть закономерность. Если число n записать в виде , то

при .

Доказательство этой гипотезы можно получить по индукции. Рассмотрим случай чётного n, тогда

.

Доказательство для случая нечётного n легко получить, если вспомнить о существовании соотношения:

.

Предыдущее рассмотрение показало важную роль степени 2 при решении нашей задачи. Предположим, что двоичное представление числа n имеет вид

,

то есть

.

В нашей задаче , все остальные равны либо 0 либо 1. Поскольку , то мы можем написать следующие равенства

,

,

,

,

.