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

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

Задача про ханойські вежі

Головоломку під назвою ханойська вежа придумав французький математик Едуард Люка в 1883 роках. Вежа являє собою вісім дисків, нанизаних в порядку зменшення розмірів на один з трьох кілочків.

Завдання полягає в тому, щоб перемістити всю вежу на один з інших кілочків, переносячи кожен раз тільки один диск і не поміщаючи більший диск на менший.

Люка пов’язував свою іграшку з міфічною легендою про значно більшій вежі Брами, яка, як стверджується, складається з 64 дисків чистого золота, а кілочки представляють собою три алмазних шпиля. При створенні світу Всевишній помістив диски на перший шпиль і повелів, щоб жерці перемістили їх на третій відповідно до запропонованими правилами. За наявними відомостями жерці трудяться над цим завданням денно і нощно – як тільки вони закінчать, вежа розсиплеться на порох і настане кінець світу.

Чи не одразу очевидно, що ця головоломка розв’язана, але по короткому роздумі (або попередньому знайомстві з цим завданням) переконуємося, що це так. Тоді виникає наступне питання: який спосіб найоптимальніший? Тобто, скільки переміщень дисків є необхідним і достатнім для виконання поставленого завдання?

Найкращий спосіб вирішити питання, подібний до нашого, – кілька узагальнити його. Вежа Брами складається з 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.

Задача про розрізування піци

Друга задача має більш відчутний геометричний присмак: скільки шматків піци можна отримати, роблячи n прямолінійних розрізів ножем? Або більш академічно: яке максимальне число Ln областей, на які площина ділиться п прямими? Вперше ця задача була вирішена в 1826 р швейцарським математиком Якобом Штейнером.

Знову почнемо з розгляду крайніх випадків, пам’ятаючи, що починати треба з самого крайнього. Площина без прямих- це одна область, з одною прямою – дві області, а з двома прямими – чотири області: