Упражнения

Разминочные упражнения

1 То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так:

„Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует лошадей (с номерами от 1 до По индуктивному предположению лошади с номерами от 1 до одинаковой масти, и, аналогично, лошади с номерами от 2 до имеют одинаковую масть. Но лошади посредине с номерами от 2 до не могут изменять масть в зависимости от того, как они сгруппированы, — это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до также должны быть одинаковой масти. Таким образом, все лошадей одинаковой масти.

Есть ли ошибка в приведенном рассуждении и какая именно?

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

3 Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения дисков на трех колышках.

4 Имеются ли какие-нибудь начальная и конечная конфигурации из дисков на трех колышках, которые требуют более чем перекладываний, чтобы получить одну из другой по исходным правилам Люка?

5 Так называемая „диаграмма Венна“ с тремя пересекающимися окружностями часто приводится для иллюстрации восьми возможных подмножеств, связанных с тремя заданными множествами:

Можно ли проиллюстрировать четырьмя пересекающимися окружностями шестнадцать возможностей, которые возникают в связи с четырьмя заданными множествами?

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

7 Пусть . В силу уравнения при всех Поэтому представляется возможным доказать индукцией по что при всех Что здесь неверно?

Домашние задания

8 Решите рекуррентное соотношение

Примите, что при всех Указание:

9 Иногда возможно использование „обратной индукции", т. е. доказательства от не наоборот! К примеру, рассмотрим утверждение

Оно справедливо для так как

а Полагая докажите, что влечет при всяком .

b Покажите, что влекут

с Объясните, почему отсюда следует справедливость при всех

10 Пусть — минимальное число перекладываний, необходимых для перемещения башни из дисков с колышка А на колышек В, если все перекладывания осуществляются по часовой стрелке — т. е. с А на В, или с В на другой колышек, или с другого колышка на А. Кроме того, пусть — минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что

(Нет необходимости решать эти рекуррентные соотношения — как это делается, мы увидим в гл. 7.)

11 Двойная ханойская башня состоит из дисков различных размеров — по два диска каждого размера. Как и в случае обычной башни, за один раз разрешается перекладывать только один диск и нельзя класть больший диск на меньший.

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

b Что если в окончательном расположении дисков требуется воспроизвести исходный порядок всех одинаковых дисков сверху донизу? [Указание: это трудно — на самом деле это „конкурсная задача"]

12 Давайте еще обобщим упр. 11а, предполагая, что имеется различных размеров дисков и ровно дисков размера к. Определите наименьшее число перекладываний дисков, необходимых для перемещения такой башни, если считать диски одинаковых размеров неразличимыми.

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

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

14 На сколько частей можно разделить головку сыра с помощью пяти плоских разрезов? (Головка сыра должна оставаться в исходном положении, пока вы ее режете, и каждому разрезу должна соответствовать некоторая плоскость в трехмерном пространстве.) Найдите рекуррентное соотношение для — максимального числа трехмерных областей, на которое может быть разбито пространство произвольно расположенными плоскостями.

15 У Иосифа был друг, которого он спас, поставив на предпоследнее спасительное место. Чему равен — номер предпоследнего выжившего, если экзекуции подлежит каждый второй?

16 Примените репертуарный метод для решения обобщенного рекуррентного соотношения с четырьмя параметрами

Указание: попробуйте функцию