85541 (589841), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

5

Z₂ = 7

Z₁ = 2

Ломаная линия подобна двум прямым с тем лишь отличием, что области сливаются, если «две» прямые не продолжать после их пересечения:

О бласти 2, 3 и 4, которые были бы разделены при наличии двух прямых, превращаются в единую область в случае одной ломаной линии, т.е. мы теряем две области. И если привести все в надлежащий порядок, то точка излома должна лежать «по ту сторону» пересечений с другими линиями, и мы теряем только две области на одну линию. Таким образом,

Z_n = L_2n − 2n = = 2n² −n+1 при n ≥ 0 (4)

Сравнивая решения в замкнутой форме (3) и (4), мы приходим к выводу, что при большом n,

L_n ~ ,

Z_n ~ 2n² ,

так что ломаные линии дают примерно в четыре раза больше областей, чем прямые.

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

Формулировка задачи: в круг выстроено 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 (5)

Теперь можно быстро продвигаться к большим 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 (6)

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

J(1) = 1

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

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 (8)

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

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

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

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

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

1. если 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

2. если 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.

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

Обратимся к двоичным представлениям величин 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)₂ (9)

т.е. 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

2 и более

Теперь давайте вернемся к нашему первоначальному предположению, что 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 - функцию, т.е. рассмотрим рекуррентность схожую с (7), но с другими константами: α, β и γ; найдем решение в замкнутой форме.

Характеристики

Список файлов ВКР