Возвратные задачи (стр. 9 из 9)
F(2n) = 2∙F(n) − 1 при n>1
Теперь посмотрим, что будет в случае, когда имеется 2n+1 людей. После первого обхода жертва с номером 1 уничтожается сразу после жертвы с номером 2n, и мы остаемся с номерами: 3, 5, 7, …, 2n−1,2n+1. Получили почти первоначальную ситуацию с nлюдьми, но на этот раз номера уцелевших удваиваются и увеличиваются на 1. Таким образом,
F(2n+1) = 2∙F(n) + 1 при n> 1
Объединение полученных равенств дает рекуррентное соотношение, которое определяет F(n) для n>3, т.к. F(1) не определено:
| n |  1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | 16 17 18 |
| F(n) | − | 2 1 | 3 5 1 3 | 5 7 9 11 1 3 5 7 | 9 11 13 |
| J(n) | 1 | 1 3 | 1 3 5 7 | 1 3 5 7 9 11 13 15 | 1 3 5 |
Если сгруппировать значения n по степеням двойки (в таблице эти группы отделены сплошными вертикальными линиями), то в каждой группе F(n) имеются еще две группы (см. таблицу). Поэтому решение рекуррентного соотношения должно иметь вид для n> 1:
Докажем полученное соотношение методом математической индукции по числу m.
1) База: n = 2, тогда m=1, k = 0
F(21+0) = J(2) + 20= 1 + 1 = 2 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤ (m − 1). Докажем для t=m:
a) если m > 0 и 2m+k= 2n, то k – четноe и
F(2m+k)= F(2∙(2m-1+
)) 
2∙F(2m-1+ ) − 1 
= 
= 
= = 
b) если m > 0 и 2m+k=2n+1, то k – нечетно (т.е. k=2t+1) и
F(2m+k) = F(2m+(2t+1)) = F(2(2m-1+t) +1)
2∙F(2m-1+ t) + 1 
= 
= 
= 
при n>0
и 
, они отличаются на n, т.к. 
. Поэтому, чтобы переложить 
перекладываний), затем перекладываем nнижних, самых больших дисков, используя только три колышка, т.к. больший диск нельзя помещать на меньший диск (потребуется 
перекладываний) и, наконец, помещаем 
Решение. Двигаясь по кругу, мы должны наказать всех «гадких парней», поэтому должны вычеркивать номера от 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 - наименьшее общее кратное этих чисел.