Возвратные задачи (стр. 4 из 9)

Из пунктов 1 и 2 следует: для n ≥ 1 f(n) = A(n)∙α + B(n)∙β + C(n)∙γ.

Теперь докажем (12) в предположении, что (11) выполняется.

Если n - четное, тогда по соотношению (10) f(2n) = 2f(n) + β. Подставляя в данное равенство соотношение (11) получим:

A(2n)∙α + B(2n)∙β + C(2n)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + β

(A(2n) − 2A(n))∙α + (B(2n) − 2B(n)−1)∙β + (C(2n) − 2C(n))∙γ = 0

Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: т.к. n = 2^m+ k=> 2n = 2^m⁺¹+2k, тогда A(2n) = 2^m⁺¹, B(2n)=2^m⁺¹−1−2k, С(n)=2k. Подставляем: (2^m⁺¹ −2∙2^m)∙α + +(2^m⁺¹−1−2k−2(2^m−1−k)−1)∙β + (2k −2k)∙γ = 0

0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно);

Если n - нечетное, тогда по соотношению (10) f(2n+1) = 2f(n) + γ. Снова подставляя в данное равенство соотношение (11) получим:

A(2n+1)∙α + B(2n+1)∙β + C(2n+1)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + γ

(A(2n+1) − 2A(n))∙α + (B(2n+1) − 2B(n))∙β + (C(2n+1) − 2C(n)−1)∙γ = 0

Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: n = 2^m+ k=> 2n+1 = 2^m⁺¹+2k+1, тогда A(2n+1) = 2^m⁺¹, B(2n+1) = 2^m⁺¹−1−(2k+1), С(n+1) = 2k+1. Подставляем : (2^m⁺¹ −2∙2^m)∙α + +(2^m⁺¹−2−2k−2(2^m−1−k))∙β + (2k+1 −2k−1)∙γ=0

0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно).

Таким образом, мы показали, что соотношения (11) и (12) верные.

Выше было показано, что J – рекуррентность имеет решение в двоичной записи: J((b_mb_m_-1 … b₁b₀)₂) = (b_m_-1 … b₁b₀b_m)₂, где b_m = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.

Запишем соотношение (10) следующим образом:

f(1) = α,

f(2n + j) = 2f(n) + β_j при j = 0, 1 и n ≥ 1,

если положить β₀ = β и β₁ = γ. Тогда:

f((b_mb_m_-1 … b₁b₀)₂) = 2f((b_mb_m_-1 … b₁)₂) + β_b

= 4f((b_mb_m_-1…b₂)₂)+2β_b+β_b= =…=2^mf((b_m)₂)+2^m^-1β_b+ … + 2β_b+β_b= 2^mα + 2^m^-1β_b+ … + 2β_b+β_b_.

Если мы расширим систему счисления с основанием 2 таким образом, что в ней допустимы произвольные числа, а не только 0 и 1, тогда предыдущий вывод означает, что

f((b_mb_m_-1 … b₁b₀)₂) = (α β_b

β_b… β_bβ_b)₂ (16)

Итак, изменение системы счисления привело нас к компактному решению (16) обобщенной рекуррентности (15).

Глава 2

Решение задач

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

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

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

Решение. Ошибка в данном рассуждении есть, и она заключается в доказательстве по индуктивному предположению. Для доказательства того, что n лошадей имеют одинаковою масть, используется пересечение двух множеств от 1 до n−1 и от 2 до n, но для n = 2 этого пересечения нет. Поэтому, если есть две лошади, имеющие разную масть, то утверждение неверно. Если же любые две лошади имеют одинаковую масть, то доказательство будет верным для любого n.

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