Возвратные задачи

a) Сколько перекладываний необходимо для перемещения двойной башни с одного колышка на другой, если диски одинаковых размеров неотличимы друг от друга?

b) Что если в окончательном расположении дисков требуется воспроизвести исходный порядок всех одинаковых дисков сверху донизу?

Решение. a) Пусть - минимальное число перекладываний башни 2n дисков с одного колышка на другой. Рассмотрим частные случаи: P₀=0, P₂=2, P₄=6, P₆=14. Эксперимент с шестью дисками дает ключ к общему правилу перемещения 2n дисков: сначала переместить (2n?2) меньших дисков с одного колышка на другой (что требует перекладываний), затем перекладываем 2 самых больших диска (одно перекладывание), потом помещаем (2n?2) меньших дисков на большие диски (что требует перекладываний). Таким образом, 2n дисков (при n>0) можно переместить за перекладываний.

Получили рекуррентное соотношение:

Решим данное соотношение. P₀ =0=, P₂ =2=, P₄ =6 = , P₆= = 14= (Здесь T_n = 2ⁿ ?1 - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка) гипотеза: при n ? 0

Докажем методом математической индукции по числу n, что при n ? 0.

1) База: n=1 (верно);

2) Индуктивный переход: пусть верно для всех чисел t ?(2n?2). Докажем для 2n дисков:

Из пунктов 1 и 2 следует, что при n ? 0.

b) Пусть - минимальное число перекладываний башни из 2n дисков с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу.

Рассмотрим частные случаи: R₀=0, R₂=3, R₄=11. Эксперимент с четырьмя дисками дает ключ к общему правилу перемещения 2n дисков в исходном порядке: сначала переместить (2n?2) меньших дисков с одного колышка на другой (что требует перекладываний), затем перекладываем два самых больших диска на свободный колышек (два перекладывания; эти диски будут положены неправильно), потом перекладываем (2n?2) меньших дисков на свободный колышек (что требует перекладываний), затем снова перекладываем два самых больших диска (два перекладывания; эти диски будут положены правильно), и, наконец, перекладываем (2n?2) меньших дисков на большие диски в исходном порядке (потребуется перекладываний). Таким образом, 2n дисков (при n>0) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за перекладываний.

Получили рекуррентное соотношение:

(*)

Решим данное соотношение. R₂ = 3 = 2P₂?1, R₄ = 11 = 2P₄?1, R₆ = 27 = 2P₆?1 гипотеза: при n > 0.

Докажем методом математической индукции по числу n, что при n > 0.

1) База: n=1 (верно);

2) Индуктивный переход: пусть верно для всех чисел t ?(2n?2). Докажем для 2n дисков:

Из пунктов 1 и 2 следует, что при n > 0.

Еще можно заметить следующее: т.к. , следовательно , то, подставляя данное равенство в соотношение (*) получим рекуррентное соотношение:

имеющее то же самое решение

Задача 12. Давайте еще обобщим задачу 11а, предполагая, что имеется n различных размеров дисков и ровно m_k дисков размера k. Определите наименьшее число A(m₁, m₂, …,m_n) перекладываний дисков, необходимых для перемещения такой башни, если считать диски одинаковых размеров неразличимыми.

Решение. Для того, что переложить башню, состоящую из n различных размеров дисков, среди которых ровно m_k дисков размера k, потребуется следующее число перекладываний:

где m_n - это количество самых больших нижних дисков.

Решим данное рекуррентное соотношение.

A(m₁)=2A(0)+m₁=m₁;

A(m₁,m₂)=2A(m₁)+m₂=2¹•m₁+m₂;

A(m₁,m₂,m₃)=2A(m₁,m₂)+m₃=2²•m₁+2¹•m₂+m₃;

A(m₁,m₂,m₃,m₄)=2A(m₁,m₂,m₃)+m₄=2³•m₁+2²•m₂+2¹•m₃+m₄.

Отсюда можно выдвинуть гипотезу, что

A(m₁,m₂,…,m_n)=

Докажем методом математической индукции по числу n.

1) База: n=1 A(m₁)=2⁰•m₁=m₁ (верно);

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

=

Из 1 и 2 следует, что A(m₁,m₂,…,m_n)=

при n > 0.

Задача 13. На какое максимально возможное число областей плоскость делится n зигзагообразными линиями, каждая из которых состоит из двух параллельных полубесконечных прямых, соединенных прямолинейным отрезком?

Решение. Пусть - это максимальное число областей, на которые плоскость делится n зигзагообразными линиями. Рассмотрим частные случаи:

(Здесь L_n = + 1 - максимальное число областей, на которые плоскость делится n прямыми)

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

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

.

Данную задачу можно решить и по другому, если заметить, что зигзаг можно рассматривать как «прямую», и отрезок, соединяющий две полупрямые, может быть сколь угодно длинным. Тогда данная задача аналогична задаче о нахождении максимального числа L_n областей, на которые плоскость делится 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, а потом с помощью этого соотношения определим, на сколько частей можно разделить головку сыра с помощью пяти плоских разрезов (головка сыра является ограниченным пространством).

Итак, рассмотрим частные случаи: Р₁=2, Р₂=4, Р₃=4+4=8, Р₄=8+7=15. Эксперимент показывает, что данная задача аналогична задаче о нахождении максимального числа L_n областей, на которые плоскость делится n прямыми (L_n=L_n-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) = 2•F(n) ? 1 при n > 3

F(2n+1) = 2•F(n) + 1 при n > 3

Решим данное рекуррентное соотношение. Составим таблицу первых значений F(n) и J(n) (здесь J(n) - номер последнего уцелевшего, когда из круга исключается каждый второй), и пусть n имеет вид: n=2^m+k, где 2^m - наибольшая степень 2, не превосходящая n (m > 0), а k - то, что остается (0 ? k < 2^m):

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(2¹+0) = J(2) + 2⁰= 1 + 1 = 2 (верно);

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

a) если m > 0 и 2^m+k = 2n, то k - четноe и

F(2^m+k)= F(2•(2^m-1+))2•F(2^m-1+) ? 1 =

= =

=

b) если m > 0 и 2^m+k=2n+1, то k - нечетно (т.е. k=2t+1) и

F(2^m+k) = F(2^m+(2t+1)) = F(2(2^m-1+t) +1) 2•F(2^m-1+ t) + 1

= =

===

Из пунктов 1 и 2 следует верность доказываемого равенства.

Задача 16. Обозначим через W_n наименьшее число перекладываний, необходимых для перемещения башни из n дисков с одного колышка на другой, когда имеется не три, а четыре колышка. Покажите, что

при n>0

(Здесь T_n = 2ⁿ ?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-ый человек, всегда ли он сможет спастись?

В работе не рассмотрен репертуарный метод решения обобщенных рекуррентностей с определенным числом параметров (т. к. не стояло такой задачи). Репертуарным методом можно, например, решить обобщенную рекуррентность с четырьмя параметрами:

Библиографический список

1. Грехем, Р. Конкретная математика. Основание информатики. [Текст] / Р. Грехем, Д. Кнут, О. Паташник. Пер. с англ. - М.:Мир, 1998. - С. 17?37.

2. Маркушевич А. И. Возвратные последовательности. Популярные лекции по математике [Текст]. - М.: Наука, 1983.

3. Мантуров О. В. Математика в понятиях, определениях и терминах. Ч.2 [Текст] / О. В. Мантуров, Ю. К. Солнцев, Ю. И. Соркин, Н. Г. Федин; Под. ред. Л. В. Сабинина. - М.: Просвещение, 1982. - С. 207-208.