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

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

    Формулировка задачи: в круг выстроено n человек, пронумерованных числами от 1 до n, и исключается каждый второй из оставшихся до тех пор, пока не уцелеет только один человек. Определить номер уцелевшего, J(n).

     Например, при n = 10 порядок исключения - 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5, т.е. J(10) = 5. При n = 2 номер уцелевшего J(2) = 1. Можно было бы предположить, что J(n) = при четном n. Однако это не   так - предположение нарушается при n = 4 и n = 6. 

      

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

    Итак, решим поставленную задачу.

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

Следующий обход будет начинаться с номера 3. Это тоже самое, если бы мы начинали с n людей, за исключением того, что номер каждого уцелевшего удваивается и уменьшается на 1. Тем самым          

     J(2n) = 2∙J(n) − 1    при n ≥ 1 (1)

    Теперь можно быстро продвигаться к большим n. Например, нам известно, что J(10) = 5, поэтому J(20) = 2∙J(10) − 1 = 2∙5 − 1 = 9, аналогично J(40) = 2∙J(20) − 1 = 17, и вообще можно вывести, что

           J(5∙2^m) = 2^m+1+1.

J(5∙2^m) = J(2∙2^m-1∙5) = 2∙J(2^m-1∙5) − 1 = 2∙J(2∙2^m-2∙5) − 1 = 2²∙J(2^m-2∙5)− 2¹ − 1 = =2³∙J(2^m-3∙5) − 2² − 2¹ − 1=2⁴∙J(2^m-4∙5) − 2³ − 2² − 2¹ − 1= …= 2^m∙J(5) − (2^m-1+2^m-2+     +…+2³+2²+2¹+1) = 2^m∙J(5) − = 2^m∙3 − 2^m + 1 = 2^m+1+1.

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

     Получили почти первоначальную ситуацию с n людьми, но на этот раз номера уцелевших удваиваются и увеличиваются на 1. Таким образом,

    J(2n+1) = 2∙J(n) + 1    при n ≥ 1 (2)

    Объединение уравнений (1) и (2) с уравнением J(1)=1 дает рекуррентное соотношение, которое определяет J во всех случаях:

                                J(1) = 1

                                J(2n) = 2∙J(n) − 1           при n ≥ 1 (3)

           J(2n+1) = 2∙J(n) + 1          при n ≥ 1

     Решим данное рекуррентное соотношение. Составим таблицу первых значений J(n): 

     

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

           J(2^m+k) = 2k+1      при  m ≥ 0  и  0 ≤ k < 2^m  (4)

(Если 2^m ≤ n < 2^m+1, то остаток k = n−2^m удовлетворяет неравенству 2^m≤k+2^m<2^m+1, т.е. 0 ≤ k < 2^m)

     Докажем (4) методом математической индукции по m.

1. База:  m = 0   =>   k = 0

                J(2⁰+0) = J(1) = 2∙0 + 1 = 1      (верно);

2. Индуктивный переход: пусть верно для всех чисел t ≤ (m − 1). Докажем для t=m:

        если m > 0 и 2^m+k=2n, то k - четно и J(2^m+k) = J(2(2^m-1+ )) = 2∙J(2^m-1+ ) − 1 2(2∙ + 1) −1 = 2k + 1

        если m > 0 и 2^m+k=2n+1, то k - нечетно (т.е. k=2t+1) и J(2^m+k) = = J(2^m+(2t+1)) = J(2(2^m-1+t) +1) 2∙J(2^m-1+ t) + 1 2(2t+1) + 1 = 2k + 1

    Другой способ доказательства, когда k - нечетно:

    Можно заметить, что  J(2n+1) − J(2n) = 2, тогда J(2^m+k) = 2 + J(2^m + (k− −1)) J(2^m+k) = 2 + 2(k −1) + 1 => J(2^m+k) = 2k+1.

    Из пунктов 1 и 2 следует:   при  m ≥ 0  и  0 ≤ k < 2^m     J(2^m+k) = 2k+1.

    Решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач. Поэтому изучим решение (4) и исследуем некоторые обобщения рекуррентного соотношения (3).

    Обратимся к двоичным представлениям величин  n и J(n) (т.к. степени 2 играли важную роль в нашем поиске решения).

                n = (b_m b_m-1 … b₁ b₀)₂ ;

    т.е.   n = b_m2^m + b_m-12^m-1 + … + b₁2 + b₀

где каждое b_i равно 0 или 1, причем старший бит b_m равен 1. Вспоминая, что n=2^m+k, последовательно получаем:

                                               n = (1 b_m-1 … b₁ b₀)₂

                                               k = (0 b_m-1 … b₁ b₀)₂

(т.к. k= n−2^m = 2^m + b_m-12^m-1 + … + b₁2 + b₀ − 2^m = 0∙2^m + b_m-12^m-1 + …+ b₁2 + b₀)

                                               2k = (b_m-1 … b₁ b₀ 0)₂

(т.к. 2 k=2(b_m-12^m-1 +b_m-22^m-2  …+ b₁2 + b₀)=b_m-12^m + b_m-22^m-1 + … + b₁2² + b₀2+0)

                2k+1 = (b_m-1 … b₁ b₀ 1)₂

                J(n) = (b_m-1 … b₁ b₀ b_m)₂

(т.к.  J(n) = 2k+1 и b_m = 1)

    Таким образом, мы получили, что

                J((b_m b_m-1 … b₁ b₀)₂) = (b_m-1 … b₁ b₀ b_m)₂ (5)

т.е. J(n) получается путем циклического сдвига двоичного представления n влево на один сдвиг.

    Рассмотрим свойства функции J(n).

    Если мы начнем с n и итерируем J-функцию m+1 раз, то тем самым осуществляем циклический сдвиг на m+1 битов, а т.к. n является (m+1)-битовым числом, то мы могли бы рассчитывать в итоге снова получить n. Но это не совсем так. К примеру, если n = 27, то J(11011) = ((10111)₂), но затем J(10111) = ((1111)₂), и процесс обрывается: когда 0 становится старшим битом - он пропадает (т.к. принято, что коэффициент при старшей степени не равен 0). В действительности J(n) всегда должно быть ≤ n по определению, т.к. J(n) есть номер уцелевшего; и если J(n) < n, мы никогда не сможем получить снова n в следующих итерациях.

    Многократное применение J порождает последовательность убывающих значений, достигающих, в конце концов «неподвижной точки» n, такой, что J(n)=n. Докажем, что J порождает последовательность убывающих значений, т.е. покажем, что 2ⁿ > 2^n-1 + 2^n-2 +…+2¹ + 1 при n ≥ 1.

    Докажем методом математической индукции по n:

1) База:  n=1,   2¹ > 2⁰  (верно);

     2) Индуктивный переход: пусть верно для всех чисел t ≤ (n-1) , т.е. выполняется неравенство 2^t-1 > 2^t-2 + 2^t-3 +…+2¹ + 1. Докажем для t=n:   

(2^n-1 > 2^n-2 + 2^n-3 +…+2¹ + 1) умножим на 2, получим 2ⁿ > 2^n-1 + 2^n-2 +…+2² + 2¹. Левая и правая части неравенства четные числа, тогда между ними есть хотя бы одно нечетное число, следовательно, прибавление 1 к правой части неравенства (четное число +1 = нечетное число) неравенство не изменит. Т.о. получаем нужное нам неравенство: 2ⁿ > 2^n-1 + 2^n-2 +…+2¹ + 1 при n ≥ 1.

     Свойство циклического сдвига позволяет выяснить, чем будет «неподвижная точка»: итерирование функции m и более раз всегда будет порождать набор из одних единиц со значением , где ν(n) - число равных 1 битов в двоичном представлении n (это следует из того, что имеем последовательность 2⁰ , 2¹ , 2² ,…,2^n-1, 2ⁿ, и по формуле суммы геометрической прогрессии получаем ). Так, например: ν(27) = ν(11011) = 4, тогда J(J(…J(27)…)) =2⁴ −1=15

    

    Теперь давайте вернемся к нашему первоначальному предположению, что J(n) = при четном n. Вообще-то это неверно, но мы выясним, когда это верно: J(n) = , тогда 2k+1 = => k = . Если число k = = целое, то n= 2^m + k будет решением, т.к. k < 2^m. Нетрудно убедиться, что (2^m − 2) кратно 3, когда m нечетно, но не когда m четно. Действительно, если m - нечетно, то 2^m − 2 = 2^2k+1 − 2 = 2(4^k − 1). Докажем методом математической индукции, что (4^k − 1) делится на три (где ):

1) База:   k=1,     4−1=3, три делится на три (верно);

    2) Индуктивный переход: пусть верно для всех чисел t ≤(k−1), т.е (4^t−1) делится на три. Докажем для t=k:

4^k − 1 = 4(4^k-1 − 1) + 3  (4^k-1 − 1) делится на три, и 3 делится на три => (4^к−1) делится на три.

    Таким образом, показали, что для m - нечетного   (2^m − 2) делится на 3.

    Теперь покажем, что при m - четном (2^m − 2) не делится на 3. Предположим противное: пусть (2^m − 2) делится на 3 при четном m, тогда , числа 2 и 3 взаимнопростые, следовательно, ( ) должно делится на 3, т.е. =3q , но , a , т.е. получили, что , а это не верно. Следовательно, наше предположение не верно и 2^m − 2 не делится на 3 при четном m.

    Таким образом, имеем бесконечно много решений уравнения J(n) = , и первые такие:

      

    Правый крайний столбец содержит двоичные числа, циклический сдвиг которых на одно позицию влево дает тот же самый результат, что и обычный сдвиг на одну позицию вправо (деление пополам).

    Далее обобщим J - функцию, т.е. рассмотрим рекуррентность схожую с (3), но с другими константами: α, β и γ; найдем решение в замкнутой форме.

                                     f(1) = α,

                f(2n) = 2f(n) + β                при n ≥ 1,  (6)

                f(2n + 1) = 2f(n) + γ           при n ≥ 1.

Составим таблицу для малых значений n:

Анализируя таблицу можно сделать предположение, что коэффициенты при α равны наибольшим степеням 2, не превосходящим n; между последовательностями 2 коэффициенты при β уменьшаются на 1 вплоть до 0, а при γ увеличиваются на 1, начиная с 0. Если выразить f(n) в виде: