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

Задача 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(2n) = J(2n+1)− J(2n)(2J(n)+1) − (2J(n)−1) = 2, a H(2n+1) = J(2n+2)− −J(2n+1) = (2J(n+1)−1)−(2J(n)+1) = 2H(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. Решите рекуррентное соотношение

                                   Q0 = α,           Q1 = β,

                        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, r Z+.

Задача 9. Иногда возможно использование «обратной индукции», т.е. доказательства от n к n−1, а не наоборот. К примеру, рассмотрим утверждение

P(n):                  ≤  ,       если  x1,x2,…,xn ≥ 0

Оно справедливо для n=2, так как

                             (x1+x2)2 − 4x1x2 = (x1−x2)2 ≥ 0.

a) Полагая , докажите, что P(n) влечет P(n−1) при всяком n > 1.

b) Покажите, что P(n) и P(2) влекут P(2n).

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):       

Страницы: 1, 2, 3, 4