Реферат: Возвратные задачи
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
Вятский государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
Возвратные задачи
Выполнила:
студентка V курса математического факультета
Ковязина Юлия Николаевна
Научный руководитель:
кандидат физико-математических наук, доцент кафедры алгебры и геометрии И.А.Семенова
Рецензент:
ст. преподаватель кафедры алгебры и геометрии
А.Н.Семенов
Допущена к защите в государственной аттестационной комиссии
«___» __________2005 г. Зав. Кафедрой Е.М. Вечтомов
«___»___________2005 г. Декан факультета В.И. Варанкина
Киров 2005
Содержание
Введение… 3
Глава 1… 6
1.1 Задача о ханойской башне… 6
1.2 Задача о разрезании пиццы… 7
1.3 Задача Иосифа Флавия… 10
Глава 2. Решение задач… 19
Заключение… 41
Библиографический список… 42
Введение
Дискретная математика в настоящее время играет большую роль в разработке принципов работы компьютера, т.к. работа компьютера представляет собой выполнение последовательности дискретных шагов, приводящих к решению поставленной перед компьютером задачи.
Рассмотренная мною тема «Возвратные задачи» является небольшой частью дискретной математики, поэтому данная тема на сегодняшний момент является не менее актуальной.
Цель моей работы – изучить имеющийся теоретический и практический материал по данной теме и применить его к решению задач.
Данная работа состоит из введения, двух глав и заключения. Во введении приводятся примеры рекуррентных соотношений, с помощью которых можно задать некоторые последовательности, а так же рекуррентные соотношения, которые могут использоваться при решении задач. В первой главе описываются три задачи: задача о ханойской башне, задача о разрезании пиццы и задача Иосифа Флавия, а также доказываются некоторые факты, которые в литературе предлагаются для самостоятельного доказательства. Вторая глава посвящена решению задач на данную тему. В заключении делаются выводы о проделанной работе и указываются дальнейшие перспективы.
В основе решения возвратных задач лежит идея возвратности (или рекуррентности), согласно которой решение всей задачи зависит от решения той же самой задачи меньших размеров.
Тема «Возвратные последовательности» не является изолированной, нигде не используемой теорией. Наоборот, возвратные последовательности близки к школьному курсу математики (арифметическая и геометрическая прогрессии, последовательности квадратов и кубов натуральных чисел и т.д.), используются в высшей алгебре, геометрии, математическом анализе и других математических дисциплинах. Теория возвратных последовательностей составляет особую главу математической дисциплины, называемой исчислением конечных разностей; представляет собой частную главу о последовательностях.
Таким образом, возвратные последовательности являются настоящей маленькой теорией, законченной, простой, ясной.
Определение: Пусть имеется последовательность {un }:
u1, u2, u3 ,…, un, … (1)
Если существует натуральное число k и числа a1, a2, a3, …,ak (действительные или мнимые) такие что, начиная с некоторого номера n и для всех следующих номеров
un+k =a1 ∙un+k-1 + a2 ∙un+k-2 +…+ak ∙un при n ≥ 1 (2)
то последовательность (1) называется возвратной последовательностью порядка k, а соотношение (2) – возвратным (рекуррентным) уравнением порядка k.
Таким образом, зная k первых членов последовательности можно определить всю последовательность, т.е. вычислить любой наперед заданный член последовательности.
С помощью рекуррентных соотношений можно задать следующие последовательности:
1). Геометрическая прогрессия
un+1 = q∙un
2). Арифметическая прогрессия
un+1 = un + d
другой вид un+2 = 2∙un+1 − un
3). Последовательность чисел Фиббоначи
un+2 = un+1 +un
4). Последовательность квадратов натуральных чисел
un+1 = un + 2∙n + 1
другой вид un+3 = 3∙un+2 − 3∙un+1 + un
5). Последовательность кубов натуральных чисел
un+4 = 4∙un+3 − 6∙un+2 +4∙un+1 − un
6). Все периодические последовательности: u1, u2, …, uk+1, …
un+k = un .
Также рекуррентные соотношения могут использоваться при решении задач (в частности, при доказательстве равенств):
7). Интегрирование простейших рациональных дробей IVтипа
ОбозначимIm = , где t = x+
Im = ∙Im-1
8). ИнтегралIn =
In =∙In-2
9). Формула длины стороны при удвоении числа сторон правильного вписанного многоугольника
an =, при n≥ 2
R– радиус описанной окружности
Если сторона a1 исходного правильного вписанного многоугольника задана, то an есть сторона многоугольника, полученного из исходного (n-1) кратным удвоением числа сторон.
10). Дифференциальные уравнения высших порядков
y(n) = f(x, y, y', y», …, y(n-1) )
11). Определитель Вандермонда
∆n =∆(x1, x2, …, xn )=
∆ (x1, x2, …, xn ) =(xn −x1 )(xn-1 −x1 )…(x2 −x1 )∙∆(x2, x3, …,xn ).
Глава 1
1.1. Задача о ханойской башне
Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск, и не помещая больший диск на меньший.
Будем решать эту задачу в общем виде, т.е. посмотрим, что будет в случае n дисков.
Будем говорить, что Tn есть минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка.
Рассмотрим крайние случаи: Т0=0, T1 =1, T2 =3, T3 =7. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n−1) меньших дисков на любой из колышков (что требует Тn-1 перекладываний), затем перекладываем самый большой диск (одно перекладывание ) и, наконец, помещаем (n−1) меньших дисков обратно на самый большой диск (еще Тn-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 2Tn-1 +1 перекладываний (т.е. достаточно перекладываний): Tn ≤ 2Tn-1 +1.
Сейчас покажем, что необходимо 2Tn-1 +1 перекладываний. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем, (n−1) меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере Тn-1 перекладываний. Самый большой диск можно перекладывать и более одного раза. Но после перемещения самого большого диска в последний раз мы обязаны поместить (n−1) меньших дисков (которые опять должны находиться на одном колышке) обратно на наибольший диск, что также требует Тn-1 перекладываний. Следовательно, Tn ≥ 2Tn-1 +1.
Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:
|
Tn = 2Tn-1 +1 при n>0
При достаточно большом n для вычисления Тn потребуется слишком много времени, поэтому получим Тn в простой, компактной, «замкнутой форме», что позволит вычислить Тn быстро.
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна).
Вычислим: Т3 =2∙3+1=7; Т4 =2∙7+1; Т5 =2∙15+1; Т6 =2∙31+1=63. Теперь можно сделать предположение, что
Тn =2n − 1 при n≥0. (2)
Докажем методом математической индукции по числу n:
1) База: n=0, Т0=20–1=1–1=0 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t≤ (n–1). Докажем для t=n: Тn = 2Tn-1 +1 2(2n-1 −1)+1 = 2∙2n-1 −2+1 = 2n − 1
Из пунктов 1 и 2 следует: при n≥0 Тn = 2n − 1
Второй способ решения.
К обеим частям соотношения (1) прибавим 1:
Т0+1 = 1,
Тn +1 = 2Tn-1 +2 при n>0.
Обозначим Un = Tn +1, тогда получим
U0 = 1
Un = 2Un-1 при n>0.
Решением этой рекурсии есть Un =2n; следовательно Тn = 2n −1.
1 .2. Задача о разрезании пиццы
Формулировка задачи: сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или, каково максимальное число Ln областей, на которые плоскость делится n прямыми?
|
Эксперимент с тремя прямыми показывает, что добавленная третья прямая может рассекать самое большое три старых области вне зависимости от того, как расположены первые две прямые:
Таким образом, L3 =4+3=7 – самое большое, что можно сделать.
Обобщая, приходим к следующему выводу: новая n-я прямая (при n>0) увеличивает число областей на k- когда рассекает k старых областей — когда пересекает прежние прямые в (k−1) различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать (n−1) старых прямых не более чем в (n−1) различных точках, и мы должны иметь k ≤ n. Установлена верхняя граница:
Ln ≤ Ln-1 + n при n>0
В этой формуле можно достичь равенства следующим образом: проводим n-ю прямую так, чтобы она не была параллельна никакой другой прямой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому рекуррентное соотношение имеет вид:
L0 = 1Ln = Ln-1 + n при n> 0
Теперь получим решение в замкнутой форме.
Ln = Ln-1 + n = Ln-2 + (n−1) + n = Ln-3 + (n−2) + (n−1) + n = … = L0+ 1 + 2+ +… + (n−2) + (n−1) + n = 1 +
Ln = + 1 при n ≥ 0 (3)
Докажем полученное равенство методом математической индукции.
1) База: n=0, L0== 1 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t≤ (n–1). Докажем для t=n:
Ln = Ln-1 + n= =
Из пунктов 1 и 2 следует: при n ≥ 0 Ln = + 1
|
|
|
|
Ломаная линия подобна двум прямым с тем лишь отличием, что области сливаются, если «две» прямые не продолжать после их пересечения:
Области 2, 3 и 4, которые были бы разделены при наличии двух прямых, превращаются в единую область в случае одной ломаной линии, т.е. мы теряем две области. И если привести все в надлежащий порядок, то точка излома должна лежать «по ту сторону» пересечений с другими линиями, и мы теряем только две области на одну линию. Таким образом,
Zn = L2n − 2n = = 2n2 −n+1 при n ≥ 0 (4)
Сравнивая решения в замкнутой форме (3) и (4), мы приходим к выводу, что при большом n,
Ln ~ ,
Zn ~ 2n2 ,
так что ломаные линии дают примерно в четыре раза больше областей, чем прямые.
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.
| N | 1 | 2 | 3 | 4 | 5 | 6 |
| J(n) | 1 | 1 | 3 | 1 | 3 | 5 |
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∙2m ) = 2m+1 +1.
J(5∙2m ) = J(2∙2m-1 ∙5) = 2∙J(2m-1 ∙5) − 1 = 2∙J(2∙2m-2 ∙5) − 1 = 22 ∙J(2m-2 ∙5)− 21 − 1 = =23 ∙J(2m-3 ∙5) − 22 − 21 − 1=24 ∙J(2m-4 ∙5) − 23 − 22 − 21 − 1= …= 2m ∙J(5) − (2m-1 +2m-2 ++…+23 +22 +21 +1) = 2m ∙J(5) − = 2m ∙3 − 2m + 1 = 2m+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 | 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | 16 |
| J(n) | 1 | 1 3 | 1 3 5 7 | 1 3 5 7 9 11 13 15 | 1 |
Если сгруппировать значения n по степеням двойки (в таблице эти группы отделены вертикальными линиями), то в каждой группе J(n) всегда будет начинаться с 1, а затем увеличиваться на 2. Итак, если записать n в виде n = 2m +k, где 2m – наибольшая степень 2, не превосходящая n, а k – то, что остается, то решение рекуррентного соотношения должно иметь вид:
J(2m +k) = 2k+1 при m≥ 0 и 0 ≤ k< 2m (8)
(Если 2m ≤ n< 2m+1, то остаток k= n−2m удовлетворяет неравенству 2m ≤k+2m <2m+1, т.е. 0 ≤ k < 2m )
Докажем (8) методом математической индукции по m.
1) База: m = 0 => k = 0
J(20+0) = J (1) = 2∙0 + 1 = 1 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤ (m − 1). Докажем для t=m:
a) если m> 0 и 2m +k=2n, то k – четно и J (2 m + k ) = J(2(2m-1 +)) = 2∙J(2m-1 +) − 1 2(2∙+ 1) −1 = 2 k + 1
b) если m > 0 и 2m +k=2n+1, то k – нечетно (т.е. k=2t+1) и J (2 m + k ) = = J(2m +(2t+1)) = J(2(2m-1 +t) +1) 2∙J(2m-1 + t) + 1 2(2t+1) + 1 = 2 k + 1
Другой способ доказательства, когда 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 < 2m J(2m +k) = 2k+1.
Решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач. Поэтому изучим решение (8) и исследуем некоторые обобщения рекуррентного соотношения (7).
Обратимся к двоичным представлениям величин nи J(n) (т.к. степени 2 играли важную роль в нашем поиске решения).
n = (bm bm-1 … b1 b0)2;
т.е. n = bm 2m + bm-1 2m-1 + … + b1 2 + 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-1 2m-1 + … + b1 2 + b0− 2m = 0∙2m + bm-1 2m-1 + …+ b1 2 + b0)
2k = (bm-1 … b1 b00)2
(т.к. 2 k=2(bm-1 2m-1 +bm-2 2m-2 …+ b1 2 + b0)=bm-1 2m + bm-2 2m-1 + … + b1 22 + b02+0)
2k+1 = (bm-1 … b1 b01)2
J(n) = (bm-1 … b1 b0bm )2
(т.к. J(n) = 2k+1 иbm = 1)
Таким образом, мы получили, что
J((bm bm-1 … b1 b0)2 ) = (bm-1 … b1 b0bm )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
|
Теперь давайте вернемся к нашему первоначальному предположению, что J(n) = при четном n. Вообще-то это неверно, но мы выясним, когда это верно: J(n) = , тогда 2k+1 = => k = . Если число k = =целое, то n= 2m + kбудет решением, т.к. k< 2m. Нетрудно убедиться, что (2m − 2) кратно 3, когда m нечетно, но не когда m четно. Действительно, если m – нечетно, то 2m − 2 = 22k+1 − 2 = 2(4k − 1). Докажем методом математической индукции, что (4k − 1) делится на три (где ):
1) База: k=1, 4−1=3, три делится на три (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤(k−1), т.е (4t −1) делится на три. Докажем для t=k:
4k − 1 = 4(4k-1 − 1) + 3 (4k-1 − 1) делится на три, и 3 делится на три => (4к −1) делится на три.
Таким образом, показали, что для m – нечетного (2m − 2) делится на 3.
Теперь покажем, что при m – четном (2m − 2) не делится на 3. Предположим противное: пусть (2m − 2) делится на 3 при четном m, тогда , числа 2 и 3 взаимнопростые, следовательно, () должно делится на 3, т.е. =3q, но , a, т.е. получили, что , а это не верно. Следовательно, наше предположение не верно и 2m − 2 не делится на 3 при четном m.
Таким образом, имеем бесконечно много решений уравнения J(n) = , и первые такие:
| m | k | N= 2m + k | J(n) =2k+1= | n (двоичное) |
| 1 | 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)∙ γ .
Из пунктов 1 и 2 следует: для n ≥ 1 f(n) = A(n)∙α + B(n)∙β + C(n)∙γ.
Теперь докажем (12) в предположении, что (11) выполняется.
Если 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 = 2m + k=> 2n = 2m+1 +2k, тогда A(2n) = 2m+1, B(2n)=2m+1 −1−2k, С(n)=2k. Подставляем: (2m+1 −2∙2m )∙α + +(2m+1 −1−2k−2(2m −1−k)−1)∙β + (2k −2k)∙γ = 0 0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно);
Если n — нечетное, тогда по соотношению (10) f(2n+1) = 2f(n) + γ. Снова подставляя в данное равенство соотношение (11) получим:
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
Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: n = 2m + k=> 2n+1 = 2m+1 +2k+1, тогда A(2n+1) = 2m+1, B(2n+1) = 2m+1 −1−(2k+1), С(n+1) = 2k+1. Подставляем: (2m+1 −2∙2m )∙α + +(2m+1 −2−2k−2(2m −1−k))∙β + (2k+1 −2k−1)∙γ=0 0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно).
Таким образом, мы показали, что соотношения (11) и (12) верные.
Выше было показано, что J – рекуррентность имеет решение в двоичной записи: J((bm bm-1 … b1 b0)2 ) = (bm-1 … b1 b0bm )2, где bm = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.
Запишем соотношение (10) следующим образом:
|
f(2n + j) = 2f(n) + βj при j = 0, 1 и n ≥ 1,
если положить β0= β и β1 = γ. Тогда:
f((bm bm-1 … b1 b0)2 ) = 2f((bm bm-1 … b1 )2 ) + βb = 4f((bm bm-1 …b2 )2 )+2βb +βb = =…=2m f((bm )2 )+2m-1 βb + … + 2βb +βb = 2m α + 2m-1 βb + … + 2βb +βb.
Если мы расширим систему счисления с основанием 2 таким образом, что в ней допустимы произвольные числа, а не только 0 и 1, тогда предыдущий вывод означает, что
f((bm bm-1 … b1 b0)2 ) = (α βb βb … βb βb )2 (16)
Итак, изменение системы счисления привело нас к компактному решению (16) обобщенной рекуррентности (15).
Глава 2
Решение задач
Задача 1. То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так:
«Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует n лошадей (с номерами от 1 до n ). По индуктивному предположению лошади с номерами от 1 до n −1 одинаковой масти, и, аналогично, лошади с номерами от 2 до n имеют одинаковую масть. Но лошади посередине с номерами от 2 до n −1 не могут изменять масть в зависимости от того, как они сгруппированы, — это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до n также должны быть одинаковой масти. Таким образом, все n лошадей одинаковой масти. Что и требовалось доказать».
Есть ли ошибка в приведенном рассуждении и, какая именно?
Решение. Ошибка в данном рассуждении есть, и она заключается в доказательстве по индуктивному предположению. Для доказательства того, что n лошадей имеют одинаковою масть, используется пересечение двух множеств от 1 до n−1 и от 2 до n, но для n = 2 этого пересечения нет. Поэтому, если есть две лошади, имеющие разную масть, то утверждение неверно. Если же любые две лошади имеют одинаковую масть, то доказательство будет верным для любого n.
Задача 2. Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек B , если прямой обмен между А и B запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя класть на меньший.)
|
|
|
Пусть Fn — минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой через колышек С.
Рассмотрим крайние случаи: F0=0, F1 =2, F2 =8, F3 =26. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n−1) меньших дисков на колышек B (что требует Fn-1 перекладываний), затем перекладываем самый большой диск на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков на колышек А (еще Fn-1 перекладываний), затем перекладываем самый большой диск на колышек B (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков на колышек B (еще Fn-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 3Fn-1 +2 перекладываний (т.е. достаточно перекладываний): Fn ≤ 3Fn-1 +2.
Сейчас покажем, что необходимо 3Fn-1 +2 перекладываний. На двух этапах мы обязаны переместить самый большой диск. Когда мы это делаем, (n−1) меньших дисков должны находиться на одном колышке (А или B), а для того чтобы собрать их вместе, потребуется, по меньшей мере, Fn-1 перекладываний. Самый большой диск можно перекладывать и более одного раза. Следовательно, Fn ≥ 3Fn-1 +2.
Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:
F0=0
Fn = 3Fn-1 +2 при n>0
Решим данное соотношение.
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим: F1 =2=31 −1, F2 =32 −1, F3 =33 −1. Из этого можно сделать предположение, что
Fn = 3n −1 при n≥0.
Докажем методом математической индукции по числу n:
1) База: n=0, F0=30–1=1–1=0 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t≤ (n–1). Докажем для t=n: Fn = 3Fn-1 +2 3(3n-1 −1)+2 = 3n − 1.
Из пунктов 1 и 2 следует: при n≥0 Fn = 3n − 1.
Второй способ решения.
К обеим частям соотношения (1) прибавим 1:
F0+1 = 1,
Fn +1 = 3Fn-1 +3 при n>0.
Обозначим Un = Fn +1, тогда получим: U0 = 1, Un = 3Un-1 при n>0.
Решением этой рекурсии есть Un =; следовательно, Fn = −1.
В дальнейшем мы не будем показывать достаточное и необходимое условие в решении подобных задач, а сразу будем описывать получение нужного равенства. Это связано, во-первых, с тем, что достаточное и необходимое условие показывается аналогично тому, как это сделано в данной задаче, а во-вторых, в виду ограниченности объема дипломной работы.
Задача 3. Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.
|
|
Существует (в соответствии с условиями задачи) только три возможных расположения каждого диска на одном из колышков: либо на первом колышке (А), либо на втором колышке (B), либо на третьем колышке (С). Это будут перестановки длины nиз трех элементов. Например, .
Число перестановок длины kиз n элементов: . Следовательно, для нашего случая , т.е. – это все возможные различные расположения n дисков на трех колышках.
В предыдущей задаче было показано, что наименьшее число перекладываний с колышка А на колышек Bчерез колышек С равно −1. Таким образом, каждый раз перекладывая диск с одного колышка на другой, мы получаем все допустимые расположения n дисков на трех колышках (т.к. мы не перекладываем один диск с одного колышка на другой по несколько раз)
Задача 4. Имеются ли какие-нибудь начальная и конечная конфигурации из n дисков на трех колышках, которые требуют более чем −1 перекладываний, чтобы получить одну из другой по исходным правилам Люка?
Решение. Докажем методом математической индукции, что любая начальная и конечная конфигурации из n дисков на трех колышках требуют не более чем −1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.
1) База: если n=1, то требуется одно перекладывание, тогда 1 ≤ 20−1 (верно);
2) Индуктивный переход: пусть для любой начальной и конечной конфигурации из n−1 дисков на трех колышках требуется не более чем −1 перекладываний. Докажем для n дисков:
· если начальная и конечная конфигурации не предполагают перекладывание самого большого нижнего диска, тогда мы перекладываем только n−1 верхних дисков, а по индуктивному предположению для этого потребуется не более чем −1 перекладываний;
· если начальная и конечная конфигурации предполагают перекладывание самого большого нижнего диска, тогда мы перекладываем n−1 верхних дисков, а по индуктивному предположению для этого будет достаточно −1 перекладываний (т.е. n−1 верхних дисков разместили на одном колышке), затем перекладываем самый большой диск (одно перекладывание), и снова перекладываем n−1 верхних дисков, как требует конечная конфигурация (достаточно −1 перекладываний). Таким образом, получили, что потребуется не более чем −1 + 1+−1=перекладываний.
Из всего этого следует, что не существует начальной и конечной конфигурации из n дисков на трех колышках требующей более чем −1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.
Задача 5. Так называемая «диаграмма Венна» с тремя пересекающимися окружностями часто приводится для иллюстрации восьми возможных подмножеств, связанных с тремя заданными множествами:
Можно ли проиллюстрировать четырьмя пересекающимися окружностями шестнадцать возможностей, которые возникают в связи с четырьмя заданными множествами?
Решение. Так как три пересекающиеся окружности иллюстрируют восемь различных подмножеств, то для того чтобы получить шестнадцать возможных подмножеств надо, чтобы четвертая окружность пересекала все восемь множеств. Но такого быть не может. Две произвольные окружности могут иметь не более двух точек пересечения, поэтому, проводя четвертую окружность, мы сможем получить максимум шесть дополнительных подмножеств. Так как возможно только два расположения четвертой окружности относительно трех данных окружностей: 1) четвертая окружность пересекает внешнее подмножество (рис. 1); 2) четвертая окружность лежит внутри трех пересекающихся окружностей (рис.2).
рис.1 рис.2
Если добавленная окружность пересекает внешнее множество, то она не сможет пересечь как минимум два внутренних множества (зависит от радиуса окружности).
Если добавленная окружность лежит внутри трех пересекающихся окружностей, то она не пересекает внешнее множество и как минимум одно внутреннее множество.
Таким образом, получили, что четырьмя окружностями можно проиллюстрировать максимум 14 (8+6=14) возможных подмножеств.
Задача 6. Некоторые из областей, очерчиваемых n прямыми на плоскости, бесконечны, в то время как другие конечны. Какое максимально возможное число конечных областей?
Решение. Пусть — максимальное число возможных конечных областей, очерчиваемых n прямыми.
Рассмотрим частные случаи (при условии, что n-я прямая не параллельна никакой другой прямой (следовательно, она пересекает каждую из них), и не проходит ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах)):
Обобщая, приходим к следующему выводу: новая n-я прямая (при n≥3) пересекает n–1 старых прямых в n−1 различных точках, следовательно, получаем n областей и две крайние из которых бесконечны. Таким образом, получили следующее рекуррентное соотношение:
|
Решим данное соотношение.
|
(Здесь Ln = + 1- максимальное число областей, на которые плоскость делится n прямыми).
Докажем полученное равенство методом математической индукции по числу n:
1) База: n=0, (верно);
2) Индуктивный переход: пусть доказано для всех чисел t≤ (n–1). Докажем для t=n: = =
=
Из пунктов 1 и 2 следует: при n ≥ 0
Задача 7. Пусть H ( n ) = J ( n +1)− J ( n ). В силу уравнения (7) (см. теорию) H (2 n ) = J (2 n +1)− J (2 n )(2 J ( n )+1) − (2 J ( n )−1) = 2, a H (2 n +1) = J (2 n +2)− − J (2 n +1) = (2 J ( n +1)−1)−(2 J ( n )+1) = 2 H ( n )−2 при всех n ≥1. Поэтому представляется возможным доказать индукцией по n , что H ( n )=2 при всех n . Что здесь не верно?
Решение. Ошибка заключается в том, что в данном рассуждении хотят доказать по индукции, что H(n)=2 при всех n (показали, что данное равенство выполняется для чисел вида 2nи 2n+1, т.к. любое натуральное число можно представить в таком виде), но при этом не проверили базу индукции (т.е. когда n принимает свое наименьшее значение: n = 1).
H(1) = J(2) − J(1) = 2J(1) −1 − J(1) = 2∙1−1−1 = 0 H(1)2база индукции не выполняется, следовательно равенство H(n)=2 верно не при всех n.
Задача 8. Решите рекуррентное соотношение
Q = α , Q 1 = β ,
Qn = при n >1.
Примите, что Qn ≠ 0 при всех n ≥ 0.
Решение. ; ;
;
;
; ;
; .
Получили: ; ; ; ; .
Обобщая, приходим к выводу, что данная последовательность периодическая: если n = 5k+r (), тогда (для n ≥ 5)
Докажем методом математической индукции:
1) База: n=5 (верно, показано выше);
n=6 (верно, показано выше);
n=7 (верно, показано выше);
n=8 (верно, показано выше);
n=9 (верно, показано выше);
2) Индуктивный переход: пусть верно для всех чисел t≤(n−1). Докажем для t=n: n= 5k + 0, тогда ;
· n = 5k + 1, тогда ;
· n = 5k + 2, тогда ;
· n = 5k + 3, тогда ;
· n = 5k + 4, тогда .
Из пунктов 1 и 2 следует: для n ≥ 5 .
Ответ: при всех n ≥ 0 и k, rZ+ .
Задача 9. Иногда возможно использование «обратной индукции», т.е. доказательства от n к n −1, а не наоборот. К примеру, рассмотрим утверждение
P ( n ): ≤ , если x 1 , x 2 ,…, xn ≥ 0
Оно справедливо для n =2, так как
( x 1 + x 2 )2 − 4 x 1 x 2 = ( x 1 − x 2 )2 ≥ 0.
a ) Полагая , докажите, что P ( n ) влечет P ( n −1) при всяком n > 1.
b ) Покажите, что P ( n ) и P (2) влекут P (2 n ).
c ) Объясните, почему отсюда следует справедливость P ( n ) при всех n .
Решение. а) подставим в P(n):
P(n): ≤
преобразуем правую скобку: =
получили: ≤
разделим левую и правую части неравенства на (эта скобка не равна нулю, т.к. x1 ,x2 ,…,xn >0 и n > 1, т.к. случай всех хi =0 тривиальный, поэтому мы его не рассматриваем)
получим P(n−1): ≤ .
Следовательно, при P(n) влечет P(n−1) при всяком n>1.
b ) запишем P(n) для двух конечных последовательностей чисел.
P(n): ≤ (для nпервых членов)
≤ (для nчленов начиная с )
перемножим эти два неравенства, используя свойство неравенств: если 0<a<bи 0<c<d, то ac<bd. Получим:
≤ .
Преобразуем правую скобку неравенства, используя утверждение Р(2)
P(2):
,
возведем левую и правую части неравенства в n-ую степень, получим
≤
Таким образом, получили:
P(2n): ≤ .
Следовательно, P(n) и P(2) влекут P(2n).
c ) Выше было показано, что из P(n) следует P(n−1), а из P(n) и P(2) следует P(2n). Следовательно, мы можем утверждать, что P(n) выполняется для любого n > 1, т.к. P(от нечетного числа n) следует из P(от четного числа (n−1)), а P(от четного числа) следует из P(2) и P(от четного или нечетного числа) и т.д., в конечном итоге приходим к P(2), а оно выполняется.
Например, P(9) следует из P(8), а P(8) следует из P(2) и P(4), P(4) следует из P(2) и P(2), а P(2) выполняется.
Задача 10. Пусть Qn — минимальное число перекладываний, необходимых для перемещения башни из n дисков с колышка А на колышек B , если все перекладывания осуществляются по часовой стрелке – т.е. с А на B , или с B на другой колышек, и с другого колышка на А. Кроме того, пусть Rn – минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что
|
|
|
|
|
|
Решение.
Рассмотрим частные случаи: Q0=0, R0=0; Q1 =1, R1 =2; Q2 =5, R2 =7; Q3 =15= =R2 +1+R2, R3 =21= Q3 +1+Q2 .
Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков cколышка А на колышек B по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка А на C, через колышек B(для этого потребуется перекладываний, т.к. это тоже самое если бы мы перекладывали диски с колышка Bна колышек А через колышек С), затем перекладываем самый большой диск cколышка A на колышек B (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка C на B(что требует перекладываний, по тем же соображениям). Таким образом, n дисков (при n>0) cколышка A на колышек B можно переместить за перекладываний. Получили соотношение:
|
|
Эксперимент с тремя дисками дает ключ и к общему правилу перемещения n дисков cколышка Bна колышек A по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка B на А (что требует Rn-1 перекладываний), затем перекладываем самый большой диск cколышка B на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка А на B(что требует Qn-1 перекладываний), затем перекладываем самый большой диск c колышек С на колышек А (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков с колышка B на колышек А (еще Rn-1 перекладываний). Таким образом, n дисков (при n>0) cколышка B на колышек А можно переместить за перекладываний. Получили соотношение:
|
|
Таким образом, получили, что системы (1) и (2) справедливы.
Задача 11. Двойная ханойская башня состоит из 2 n дисков n различных размеров – по два диска каждого размера. Как и в случае обычной башни, за один раз разрешается перекладывать только один диск и нельзя класть больший диск на меньший.
a ) Сколько перекладываний необходимо для перемещения двойной башни с одного колышка на другой, если диски одинаковых размеров неотличимы друг от друга?
b ) Что если в окончательном расположении дисков требуется воспроизвести исходный порядок всех одинаковых дисков сверху донизу?
Решение. a ) Пусть — минимальное число перекладываний башни 2n дисков с одного колышка на другой. Рассмотрим частные случаи: P0=0, P2 =2, P4 =6, P6 =14. Эксперимент с шестью дисками дает ключ к общему правилу перемещения 2n дисков: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует перекладываний), затем перекладываем 2 самых больших диска (одно перекладывание), потом помещаем (2n−2) меньших дисков на большие диски (что требует перекладываний). Таким образом, 2n дисков (при n>0) можно переместить за перекладываний.
Получили рекуррентное соотношение:
|
Решим данное соотношение. P0 =0=, P2 =2=, P4 =6 = , P6 == 14=(Здесь Tn = 2n −1 — минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка) гипотеза: при n≥ 0
Докажем методом математической индукции по числу n, что при n≥ 0.
1) База: n=1 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤(2n−2). Докажем для 2n дисков:
Из пунктов 1 и 2 следует, что при n ≥ 0.
b ) Пусть — минимальное число перекладываний башни из 2n дисков с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу.
Рассмотрим частные случаи: R0=0, R2 =3, R4 =11. Эксперимент с четырьмя дисками дает ключ к общему правилу перемещения 2n дисков в исходном порядке: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует перекладываний), затем перекладываем два самых больших диска на свободный колышек (два перекладывания; эти диски будут положены неправильно), потом перекладываем (2n−2) меньших дисков на свободный колышек (что требует перекладываний), затем снова перекладываем два самых больших диска (два перекладывания; эти диски будут положены правильно), и, наконец, перекладываем (2n−2) меньших дисков на большие диски в исходном порядке (потребуется перекладываний). Таким образом, 2n дисков (при n>0) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за перекладываний.
Получили рекуррентное соотношение:
|
Решим данное соотношение. R2 = 3 = 2P2 −1, R4 = 11 = 2P4 −1, R6 = 27 = 2P6 −1 гипотеза: при n > 0.
Докажем методом математической индукции по числу n, что при n> 0.
1) База: n=1 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤(2n−2). Докажем для 2n дисков:
Из пунктов 1 и 2 следует, что при n> 0.
|
имеющее то же самое решение
Задача 12. Давайте еще обобщим задачу 11а, предполагая, что имеется n различных размеров дисков и ровно mk дисков размера k . Определите наименьшее число A ( m 1 , m 2 , …, mn ) перекладываний дисков, необходимых для перемещения такой башни, если считать диски одинаковых размеров неразличимыми.
Решение. Для того, что переложить башню, состоящую из nразличных размеров дисков, среди которых ровно mk дисков размера k, потребуется следующее число перекладываний:
|
где mn – это количество самых больших нижних дисков.
Решим данное рекуррентное соотношение.
A(m1 )=2A(0)+m1 =m1 ;
A(m1 ,m2 )=2A(m1 )+m2 =21 ∙m1 +m2 ;
A(m1 ,m2 ,m3 )=2A(m1 ,m2 )+m3 =22 ∙m1 +21 ∙m2 +m3 ;
A(m1 ,m2 ,m3 ,m4 )=2A(m1 ,m2 ,m3 )+m4 =23 ∙m1 +22 ∙m2 +21 ∙m3 +m4 .
Отсюда можно выдвинуть гипотезу, что
|
Докажем методом математической индукции по числу n.
1) База: n=1 A(m1 )=20∙m1 =m1 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤(n−1). Докажем для t=n: =2∙()
=
Из 1 и 2 следует, что A(m1 ,m2 ,…,mn )=
при n > 0.
Задача 13. На какое максимально возможное число областей плоскость делится n зигзагообразными линиями, каждая из которых состоит из двух параллельных полубесконечных прямых, соединенных прямолинейным отрезком?
Решение. Пусть — это максимальное число областей, на которые плоскость делится n зигзагообразными линиями. Рассмотрим частные случаи:
(Здесь Ln = + 1- максимальное число областей, на которые плоскость делится n прямыми)
Из этих частных случаев можно видеть, что зигзагообразная линия подобна трем прямым с тем лишь отличием, что области сливаются, если «три» прямые не продолжать после их пересечения:
Области 1, 2, 6 и 3, 4, 5, которые были бы разделены при наличии трех прямых, превращаются в единую область в случае одной зигзагообразной линии, т.е. мы теряем четыре области. Так же у нас имеется две параллельные прямые, следовательно, мы теряем еще одну область. Таким образом, если привести все в надлежащий порядок, то все зигзагообразные линии должны пересекаться между собой и точки изломов должны лежать «по ту сторону» пересечений с другими линиями, и мы теряем только пять областей на одну линию. Таким образом,
.
Данную задачу можно решить и по другому, если заметить, что зигзаг можно рассматривать как «прямую», и отрезок, соединяющий две полупрямые, может быть сколь угодно длинным. Тогда данная задача аналогична задаче о нахождении максимального числа Ln областей, на которые плоскость делится n прямыми (две прямые имеют одну точку пересечения). В нашем случае две зигзагообразные линии имеют девять точек пересечения.
С другой стороны, две зигзагообразные линии подобны шести прямым с тем лишь отличием, что области сливаются, если «шесть» прямых не продолжать после их пересечения,
Эти шесть прямых образуют 20 областей, следовательно, при пересечении двух зигзагообразных линий мы теряем восемь областей.
Таким образом, получаем рекуррентное соотношение:
|
Решим данное соотношение. +9n−
−8=
+9∙(n−1)−8+9n−8=
=при n ≥ 0.
Докажем полученное равенство методом математической индукции.
1) База: n=0, (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤ (n–1). Докажем для t=n: = +9n−7=.
Из пунктов 1 и 2 следует: при n> 0 .
Задача 14. На какое максимальное число частей можно разделить головку сыра с помощью пяти плоских разрезов? (Головка сыра должна оставаться в исходном положении, пока вы ее режете, и каждому разрезу должна соответствовать некоторая плоскость в трехмерном пространстве.) Найдите рекуррентное соотношение для Р n — максимального числа трехмерных областей, на которое может быть разбито пространство n произвольно расположенными плоскостями.
Решение. Сначала найдем рекуррентное соотношение для Рn, а потом с помощью этого соотношения определим, на сколько частей можно разделить головку сыра с помощью пяти плоских разрезов (головка сыра является ограниченным пространством).
Итак, рассмотрим частные случаи: Р1 =2, Р2 =4, Р3 =4+4=8, Р4 =8+7=15. Эксперимент показывает, что данная задача аналогична задаче о нахождении максимального числа Ln областей, на которые плоскость делится n прямыми (Ln =Ln-1 +n), но только с тем отличием, что дело обстоит в пространстве. Две произвольные плоскости пересекаются по единственной прямой, и для того, чтобы получить максимальное число трехмерных областей надо, чтобы каждая новая проведенная плоскость не была параллельна никакой другой плоскости (следовательно, она пересекает каждую из них), и не проходила ни через одну из имеющихся прямых пересечения (следовательно, она пересекает каждую из плоскостей по различным прямым). Таким образом, проводя новую n-ую плоскость, мы к старым областям добавляем столько трехмерных областей, сколько образуется областей на n-ой плоскости образованных прямой пересечения этой плоскости со всеми остальными плоскостями. Поэтому рекуррентное соотношение имеет вид:
Следовательно, головку сыра можно разделить с помощью пяти плоских разрезов не более чем на 26 частей.
Задача 15. У Иосифа был друг, которого он спас, поставив на предпоследнее спасительное место. Чему равен F ( n ) — номер предпоследнего выжившего, если экзекуции подлежит каждый второй?
Решение. Допустим, что первоначально имеется 2n людей. После первого обхода мы остаемся с номерами: 1, 3, 5, 7, …, 2n−3, 2n−1. Следующий обход будет начинаться с номера 3. Это то же самое, если бы мы начинали с n людей, за исключением того, что номер каждого уцелевшего удваивается и уменьшается на 1. Тем самым
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 = 2 n −1 — число перекладываний в обычном случае трех колышков.)
Решение. Посмотрим на числа и , они отличаются на n, т.к. . Поэтому, чтобы переложить дисков с одного колышка на другой, имея в распоряжении четыре колышка, надо: сначала переместить меньших дисков на любой из колышков, используя все четыре колышка (что требует перекладываний), затем перекладываем nнижних, самых больших дисков, используя только три колышка, т.к. больший диск нельзя помещать на меньший диск (потребуется перекладываний) и, наконец, помещаем меньших дисков обратно на самые большие диски, используя снова четыре колышка (еще перекладываний). Таким образом, для перемещения дисков (при n>0) достаточно следующее число перекладываний: .
Задача 17. Допустим, что в круг поставлено 2 n человек, первые 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-ый человек, всегда ли он сможет спастись?
В работе не рассмотрен репертуарный метод решения обобщенных рекуррентностей с определенным числом параметров (т. к. не стояло такой задачи). Репертуарным методом можно, например, решить обобщенную рекуррентность с четырьмя параметрами:
|
Библиографический список
1. Грехем, Р. Конкретная математика. Основание информатики. [Текст] / Р. Грехем, Д. Кнут, О. Паташник. Пер. с англ. – М.: Мир, 1998. – С. 17−37.
2. Маркушевич А. И. Возвратные последовательности. Популярные лекции по математике [Текст]. — М.: Наука, 1983.
3. Мантуров О. В. Математика в понятиях, определениях и терминах. Ч.2 [Текст] / О. В. Мантуров, Ю. К. Солнцев, Ю. И. Соркин, Н. Г. Федин; Под. ред. Л. В. Сабинина. – М.: Просвещение, 1982. – С. 207–208.