Быстрый поиск

Дипломная работа: Возвратные задачи

Сейчас покажем, что необходимо 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 дисков на трех колышках.

2

1

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

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

при n≥3

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

при n≥0.

(Здесь 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.