Звороті задачі

Ці завдання мають дві спільні риси: до них неодноразово зверталися математики і рішення кожної з них засноване на ідеї повернення (або рекурентності), згідно з якою рішення всієї задачі залежить від рішень того ж самого завдання менших розмірів.

Найкращий спосіб вирішити питання, подібний до нашого, – кілька узагальнити його. Вежа Брами складається з 64 дисків, а ханойська вежа -з 8; подивимося, що буде в разі n дисків.

Одна з переваг такого роду узагальнення полягає в тому, що можна буде навіть ще зменшити розмір завдання.

Наступний крок у вирішенні завдання -вибір відповідного позначення: позначає І ВЛАДАРЮЙ. Будемо говорити, що Тn є мінімальне число перекладань, необхідних для переміщення п дисків з одного кілочка на інший за правилами Люка. Тоді Т1, очевидно, дорівнює 1, а Т2 дорівнює 3.

Можна отримати додаткову інформацію, причому абсолютно безкоштовно, якщо розглянути самий крайній випадок: ясно, що То = 0, оскільки для переміщення вежі з n = О дисків взагалі не потрібно жодного перекладання! Блискучі математики не соромились впадати в крайнощі, бо якщо гарненько розібратися в окремих випадках (навіть в зовсім тривіальних), легше осягнути загальні закономірності.

Але давайте тепер змінимо точку зору і спробуємо подумати про головне – як перемістити вежу? Експерименти з трьома дисками показують, що вирішальна ідея полягає в перенесенні двох верхніх дисків на середній кілочок; потім переноситься третій диск і на нього поміщаються два інших. Це дає ключ до загальним правилом переміщення п дисків: спочатку ми переміщаємо n – 1 менших дисків на будь-який з кілочків (що вимагає Tn-1 перекладань), потім перекладаємо найбільший диск (одне перекладання) і, нарешті, поміщаємо n – 1 менших дисків назад на найбільший диск (ще Тn-1 перекладань). Таким чином, n дисків (при n> 0) можна перемістити найбільше за 2Tn-i + 1 перекладань:

Tn  ≥ 2Tn-1 +1 при n >0.