Возвратные задачи (стр. 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) не определено:
F(2n+1) = 2∙F(n) + 1 при n> 3
Решим данное рекуррентное соотношение. Составим таблицу первых значений F(n) и J(n) (здесь J(n) - номер последнего уцелевшего, когда из круга исключается каждый второй), и пусть n имеет вид: n=2m+k, где 2m – наибольшая степень 2, не превосходящая n (m> 0), а k – то, что остается (0 ≤ k < 2m):
| 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 
=
=
=Из пунктов 1 и 2 следует верность доказываемого равенства.
Задача 16.Обозначим через Wn наименьшее число перекладываний, необходимых для перемещения башни из nдисков с одного колышка на другой, когда имеется не три, а четыре колышка. Покажите, что
при n>0(Здесь Tn = 2n−1 - число перекладываний в обычном случае трех колышков.)
Решение. Посмотрим на числа
и 
, они отличаются на n, т.к. 
. Поэтому, чтобы переложить дисков с одного колышка на другой, имея в распоряжении четыре колышка, надо: сначала переместить меньших дисков на любой из колышков, используя все четыре колышка (что требует 
перекладываний), затем перекладываем nнижних, самых больших дисков, используя только три колышка, т.к. больший диск нельзя помещать на меньший диск (потребуется 
перекладываний) и, наконец, помещаем меньших дисков обратно на самые большие диски, используя снова четыре колышка (еще перекладываний). Таким образом, для перемещения дисков (при n>0) достаточно следующее число перекладываний: .Задача 17.Допустим, что в круг поставлено 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 - наименьшее общее кратное этих чисел.Заключение
В данной работе поставленные цели были достигнуты. Однако тема далеко не исчерпана. Имеются перспективы в виде обобщения или изменения условий некоторых задач, и их последующего решения. Например, задачу о «диаграммах Венна» можно обобщить, рассматривая не окружности, а овалы или выпуклые многоугольники, и для них определить, какое максимальное число возможных подмножеств с их помощью можно проиллюстрировать. Задачу Иосифа Флавия можно изменить, например, так: Иосиф занимает конкретное j-е место и может назвать роковой параметр q, после чего уничтожается каждый q-ый человек, всегда ли он сможет спастись?
В работе не рассмотрен репертуарный метод решения обобщенных рекуррентностей с определенным числом параметров (т. к. не стояло такой задачи). Репертуарным методом можно, например, решить обобщенную рекуррентность с четырьмя параметрами:
