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

f(n) = A(n)∙α + B(n)∙β + C(n)∙γ                   (7)

то, по-видимому,

A(n) = 2^m ,

B(n) = 2^m −1−k,                         (8)

                                       С(n) = k.

Здесь n = 2^m + k       и      0 ≤ k < 2^m            при n ≥ 1.

    Докажем соотношения (7) и (8).

    Докажем (7) методом математической индукции по числу n и при этом будем полагать, что (8) выполняется.

    1) База:   n=1=2⁰+0 (m=k=0),   f(1)=A(1)∙α+B(1)∙β+C(1)∙γ= =2⁰∙α+(2⁰−1−0)∙β+0∙γ = α (верно);

    2) Индуктивный переход: пусть верно для всех чисел t ≤ (n-1) , т.е. выполняется равенство f(t) = A(t)∙α + B(t)∙β + C(t)∙γ. Докажем для t=n:

     a) если n - четное, тогда k тоже четное, т.е. k = 2t, и f(n) = f(2^m+2t) = =f(2(2^m-1 + t)) 2∙f(2^m-1 + t)+β 2∙(A(2^m-1 + t)∙α + B(2^m-1 + t)∙β + C(2^m-1 + +t)∙γ) + β 2(2^m-1∙α + (2^m-1−1−t)∙β + t∙γ) + β = 2^m∙α + (2^m−1−2t)∙β + 2t∙γ = 2^m∙α+ + (2^m−1−k)∙β + k∙γ = A(n)∙α + B(n)∙β + C(n)∙γ;

     b) если n - нечетное, тогда k тоже нечетно, т.е. k=2t+1, и f(n) = =f(2^m+2t+1) = f(2(2^m-1 + t)+1) 2∙f(2^m-1 + t)+ γ 2∙(A(2^m-1 + t)∙α + B(2^m-1 + +t)∙β + C(2^m-1 + t)∙γ) + γ 2(2^m-1∙α + (2^m-1−1−t)∙β + t∙γ) + γ = 2^m∙α + +(2^m−1−(2t+1))∙β + (2t+1)∙γ = 2^m∙α+ + (2^m−1−k)∙β + k∙γ = A(n)∙α + B(n)∙β + C(n)∙γ.

    Из пунктов 1 и 2 следует: для n ≥ 1      f(n) = A(n)∙α + B(n)∙β + C(n)∙γ.

Теперь докажем (8) в предположении, что (7) выполняется.

    Если n - четное, тогда по соотношению (10) f(2n) = 2f(n) + β. Подставляя в данное равенство соотношение (11) получим:

      A(2n)∙α + B(2n)∙β + C(2n)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + β

      (A(2n) − 2A(n))∙α + (B(2n) − 2B(n)−1)∙β + (C(2n) − 2C(n))∙γ = 0

Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: т.к. n = 2^m + k => 2n = 2^m+1+2k, тогда A(2n) = 2^m+1 , B(2n)=2^m+1−1−2k, С(n)=2k. Подставляем: (2^m+1 −2∙2^m)∙α + +(2^m+1−1−2k−2(2^m−1−k)−1)∙β + (2k −2k)∙γ = 0 0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно);

    Если n - нечетное, тогда по соотношению (6) f(2n+1) = 2f(n) + γ. Снова подставляя в данное равенство соотношение (7) получим:

      A(2n+1)∙α + B(2n+1)∙β + C(2n+1)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + γ

(A(2n+1) − 2A(n))∙α + (B(2n+1) − 2B(n))∙β + (C(2n+1) − 2C(n)−1)∙γ = 0

Теперь подставим соотношение (8) в данное равенство и посмотрим, будет ли оно выполнятся:  n = 2^m + k => 2n+1 = 2^m+1+2k+1, тогда A(2n+1) = 2^m+1 , B(2n+1) = 2^m+1 −1−(2k+1),       С(n+1) = 2k+1. Подставляем : (2^m+1 −2∙2^m)∙α + +(2^m+1−2−2k−2(2^m−1−k))∙β + (2k+1 −2k−1)∙γ=0 0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно).

    Таким образом, мы показали, что соотношения (7) и (8) верные.

    Выше было показано, что J - рекуррентность имеет решение в двоичной записи: J((b_m b_m-1 … b₁ b₀)₂) = (b_m-1 … b₁ b₀ b_m)₂,   где b_m = 1. Можно показать, что и обобщенная рекуррентность (6) имеет похожее решение.

    Запишем соотношение (6) следующим образом:

                    f(1) = α,

                f(2n + j) = 2f(n) + β_j         при j = 0, 1     и     n ≥ 1,

если положить β₀ = β и β₁ = γ. Тогда:

f((b_m b_m-1 … b₁ b₀)₂) = 2f((b_m b_m-1 … b₁)₂) + β_b = 4f((b_mb_m-1…b₂)₂)+2β_b +β_b = =…=2^mf((b_m)₂)+2^m-1β_b + … + 2β_b +β_b = 2^m α + 2^m-1β_b + … + 2β_b +β_{b .}

    Если мы расширим систему счисления с основанием 2 таким образом, что в ней допустимы произвольные числа, а не только 0 и 1, тогда предыдущий вывод означает, что

          f((b_m b_m-1 … b₁ b₀)₂) = (α β_b β_b … β_b β_b )₂   (10)

    Итак, изменение системы счисления привело нас к компактному решению (10) обобщенной рекуррентности (9). 
 
 
 

    Задача. Допустим, что в круг поставлено 2n человек, первые n из которых - «славные ребята», а n последних - «гадкие парни». Покажите, что всегда найдется целое m (зависящее от n), такое, что если, двигаясь по кругу, мы наказываем каждого m-го, то первыми будут наказаны все гадкие парни. (К примеру, при n=3 можно взять m=5, а при n=4 взять m=30.)

     Решение. Двигаясь по кругу, мы должны наказать всех «гадких парней», поэтому должны вычеркивать номера от n+1 до 2n. Если мы вычеркнем в первый раз номер 2n, то в круге останется 2n−1 человек, и следующий круг начнем с номера 1 (для того, чтобы вычеркнуть номер 2n мы должны обойти целое число кругов). Если во второй раз мы вычеркнем номер 2n−1, то в круге останется 2n−2 человек, и снова, следующий круг будем начинать с номера 1 (для того, чтобы вычеркнуть номер 2n−1 мы снова должны обойти целое число кругов). И так далее, будем поочередно вычеркивать номера 2n−2, 2n−3, …, n+1 (а для этого мы должны каждый раз между вычеркивания «гадких парней» проходить целое число кругов) и каждый раз после вычеркивания количество человек уменьшается на единицу, и новый круг будем начинать с номера 1. Поэтому надо взять такое число m, которое делилось бы на 2n, 2n−1, …, n+1. Например, можно взять m - наименьшее общее кратное этих чисел.