85541 (Возвратные задачи), страница 4

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

Решение. Докажем методом математической индукции, что любая начальная и конечная конфигурации из n дисков на трех колышках требуют не более чем −1 перекладываний, чтобы получить одну из другой по исходным правилам Люка.

1. База: если n=1, то требуется одно перекладывание, тогда 1 ≤ 2⁰−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.

(Здесь L_n = + 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. Решите рекуррентное соотношение

Q₀ = α, Q₁ = β,

Q_n = при n>1.

Примите, что Q_n ≠ 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): ≤ , если x₁,x₂,…,x_n ≥ 0

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

(x₁+x₂)² − 4x₁x₂ = (x₁−x₂)² ≥ 0.

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

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

c) Объясните, почему отсюда следует справедливость P(n) при всех n.

Решение. а) подставим в P(n):

P(n): ≤

преобразуем правую скобку: =

получили: ≤

разделим левую и правую части неравенства на (эта скобка не равна нулю, т.к. x₁,x₂,…,x_n >0 и n > 1, т.к. случай всех х_i=0 тривиальный, поэтому мы его не рассматриваем )

получим P(n−1): ≤ .

Следовательно, при P(n) влечет P(n−1) при всяком n>1.

b) запишем P(n) для двух конечных последовательностей чисел.

P(n): ≤ (для n первых членов)

≤ (для n членов начиная с )

перемножим эти два неравенства, используя свойство неравенств: если 0

≤ .

Преобразуем правую скобку неравенства, используя утверждение Р(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. Пусть Q_n - минимальное число перекладываний, необходимых для перемещения башни из n дисков с колышка А на колышек B, если все перекладывания осуществляются по часовой стрелке – т.е. с А на B, или с B на другой колышек, и с другого колышка на А. Кроме того, пусть R_n – минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что

если n > 0

если n = 0

(1)

если n > 0

если n = 0

(2)

Р ешение.

Рассмотрим частные случаи: Q₀=0, R₀=0; Q₁=1, R₁=2; Q₂=5, R₂=7; Q₃=15= =R₂+1+R₂, R₃=21= Q₃+1+Q₂.

Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков c колышка А на колышек B по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка А на C, через колышек B (для этого потребуется перекладываний, т.к. это тоже самое если бы мы перекладывали диски с колышка B на колышек А через колышек С), затем перекладываем самый большой диск c колышка A на колышек B (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка C на B (что требует перекладываний, по тем же соображениям). Таким образом, n дисков (при n>0) c колышка A на колышек B можно переместить за перекладываний. Получили соотношение:

если n > 0

если n = 0

Эксперимент с тремя дисками дает ключ и к общему правилу перемещения n дисков c колышка B на колышек A по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка B на А (что требует R_n-1 перекладываний), затем перекладываем самый большой диск c колышка B на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка А на B (что требует Q_n-1 перекладываний), затем перекладываем самый большой диск c колышек С на колышек А (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков с колышка B на колышек А (еще R_n-1 перекладываний). Таким образом, n дисков (при n>0) c колышка B на колышек А можно переместить за перекладываний. Получили соотношение:

И

если n > 0

если n = 0

если мы вместо подставим (т.к. , показали выше), то получим нужную нам систему:

Таким образом, получили, что системы (1) и (2) справедливы.

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

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

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

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

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