Возвратные задачи (стр. 3 из 9)
Другой способ доказательства, когда k – нечетно:
Можно заметить, что J(2n+1) − J(2n) = 2, тогда J(2m+k) = 2 + J(2m+ (k− −1))
J(2m+k) = 2 + 2(k −1) + 1 => J(2m+k) = 2k+1.Из пунктов 1 и 2 следует: при m ≥ 0 и 0 ≤ k < 2mJ(2m+k) = 2k+1.
Решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач. Поэтому изучим решение (8) и исследуем некоторые обобщения рекуррентного соотношения (7).
Обратимся к двоичным представлениям величин nи J(n) (т.к. степени 2 играли важную роль в нашем поиске решения).
n = (bm bm-1 … b1 b0)2 ;
т.е. n = bm2m + bm-12m-1 + … + b12 + b0
где каждое bi равно 0 или 1, причем старший бит bm равен 1. Вспоминая, что n=2m+k, последовательно получаем:
n = (1 bm-1 … b1 b0)2
k = (0 bm-1 … b1 b0)2
(т.к. k= n−2m = 2m + bm-12m-1 + … + b12 + b0 − 2m = 0∙2m + bm-12m-1 + …+ b12 + b0)
2k = (bm-1 … b1 b0 0)2
(т.к. 2 k=2(bm-12m-1 +bm-22m-2 …+ b12 + b0)=bm-12m + bm-22m-1 + … + b122 + b02+0)
2k+1 = (bm-1 … b1 b0 1)2
J(n) = (bm-1 … b1 b0 bm)2
(т.к. J(n) = 2k+1 иbm = 1)
Таким образом, мы получили, что
J((bm bm-1 … b1 b0)2) = (bm-1 … b1 b0 bm)2 (9)
т.е. J(n) получается путем циклического сдвига двоичного представления n влево на один сдвиг.
Рассмотрим свойства функции J(n).
Если мы начнем с n и итерируем J-функцию m+1 раз, то тем самым осуществляем циклический сдвиг на m+1 битов, а т.к. nявляется (m+1)-битовым числом, то мы могли бы рассчитывать в итоге снова получить n. Но это не совсем так. К примеру, если n = 27, то J(11011) = ((10111)2), но затем J(10111) = ((1111)2), и процесс обрывается: когда 0 становится старшим битом – он пропадает (т.к. принято, что коэффициент при старшей степени не равен 0). В действительности J(n) всегда должно быть ≤ n по определению, т.к. J(n) есть номер уцелевшего; и если J(n) < n, мы никогда не сможем получить снова n в следующих итерациях.
Многократное применение J порождает последовательность убывающих значений, достигающих, в конце концов «неподвижной точки» n, такой, что J(n)=n. Докажем, что J порождает последовательность убывающих значений, т.е. покажем, что 2n> 2n-1 + 2n-2 +…+21 + 1 при n≥ 1.
Докажем методом математической индукции по n:
1) База: n=1, 21 > 20 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤ (n–1) , т.е. выполняется неравенство 2t-1 > 2t-2 + 2t-3 +…+21 + 1. Докажем для t=n:
(2n-1 > 2n-2 + 2n-3 +…+21 + 1) умножим на 2, получим 2n> 2n-1 + 2n-2 +…+22 + 21. Левая и правая части неравенства четные числа, тогда между ними есть хотя бы одно нечетное число, следовательно, прибавление 1 к правой части неравенства (четное число +1 = нечетное число) неравенство не изменит. Т.о. получаем нужное нам неравенство: 2n> 2n-1 + 2n-2 +…+21 + 1 при n ≥ 1.
Свойство циклического сдвига позволяет выяснить, чем будет «неподвижная точка»: итерирование функции m и более раз всегда будет порождать набор из одних единиц со значением 
, где ν(n) – число равных 1 битов в двоичном представлении n (это следует из того, что имеем последовательность 20 , 21 , 22 ,…,2n-1, 2n, и по формуле суммы геометрической прогрессии получаем 
). Так, например: ν(27) = ν(11011) = 4, тогда J(J(…J(27)…)) =24 −1=15 
=> k = 
. Если число k = = 
):
(4k-1 − 1) делится на три, и 3 делится на три => (4к−1) делится на три.
, числа 2 и 3 взаимнопростые, следовательно, ( 
) должно делится на 3, т.е. 
, но 
, a 
, т.е. получили, что 
, а это не верно. Следовательно, наше предположение не верно и 2m − 2 не делится на 3 при четном m.| m | k | N= 2m + k | J(n) =2k+1=  | n (двоичное) |
| 1 | 0 | 2 | 1 | 10 |
| 3 | 2 | 10 | 5 | 1010 |
| 5 | 10 | 42 | 21 | 101010 |
| 7 | 42 | 170 | 85 | 10101010 |
Правый крайний столбец содержит двоичные числа, циклический сдвиг которых на одно позицию влево дает тот же самый результат, что и обычный сдвиг на одну позицию вправо (деление пополам).
Далее обобщим J - функцию, т.е. рассмотрим рекуррентность схожую с (7), но с другими константами: α, β и γ; найдем решение в замкнутой форме.
f(1) = α,
f(2n) = 2f(n) + β при n ≥ 1, (10)
f(2n + 1) = 2f(n) + γ при n ≥ 1.
Составим таблицу для малых значений n:
Анализируя таблицу можно сделать предположение, что коэффициенты при α равны наибольшим степеням 2, не превосходящим n; между последовательностями 2 коэффициенты при β уменьшаются на 1 вплоть до 0, а при γ увеличиваются на 1, начиная с 0. Если выразить f(n) в виде:f(n) = A(n)∙α + B(n)∙β + C(n)∙γ (11)
то, по-видимому,
A(n) = 2m,
B(n) = 2m−1−k,(12)
С(n) = k.
Здесь n = 2m+ k и 0 ≤ k < 2mпри n ≥ 1.
Докажем соотношения (11) и (12).
Докажем (11) методом математической индукции по числу nи при этом будем полагать, что (12) выполняется.
1) База: n=1=20+0 (m=k=0), f(1)=A(1)∙α+B(1)∙β+C(1)∙γ= =20∙α+(20−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(2m+2t) = =f(2(2m-1 + t))
2∙f(2m-1 + t)+β 
2∙(A(2m-1 + t)∙α + B(2m-1 + t)∙β + C(2m-1 + +t)∙γ) + β 
2(2m-1∙α + (2m-1−1−t)∙β + t∙γ) + β = 2m∙α + (2m−1−2t)∙β + 2t∙γ = 2m∙α+ + (2m−1−k)∙β + k∙γ = A(n)∙α + B(n)∙β + C(n)∙γ;b) еслиn - нечетное, тогдаk тоженечетно, т.е. k=2t+1, иf(n) = =f(2m+2t+1) = f(2(2m-1 + t)+1)
2∙f(2m-1 + t)+ γ 2∙(A(2m-1 + t)∙α + B(2m-1 + +t)∙β + C(2m-1 + t)∙γ) + γ 2(2m-1∙α + (2m-1−1−t)∙β + t∙γ) + γ = 2m∙α + +(2m−1−(2t+1))∙β + (2t+1)∙γ = 2m∙α+ + (2m−1−k)∙β + k∙γ = A(n)∙α + B(n)∙β + C(n)∙γ.