Що ж являє собою ця головоломка, яку іноді називають «Вежею брамінів», а Е. Ігнатьєв називає «Дитячої пірамідкою»? Якщо ви візьмете дитячу піраміду (диски розташовуються в порядку зростання: верхній - найменший, а нижній - найбільший) і ще два стержня від таких же дитячих пірамід, то головоломка вже у вас в руках.
Занумеруем стрижні: той, на якому знаходяться диски, отримає номер 1, інші - номери 2 і 3. Завдання полягає в тому, щоб перенести диски зі стрижня 1 на стрижень 3, використовуючи стрижень 2, як проміжний. При цьому повинні дотримуватися дві умови:
- за один хід можна переносити лише один диск,
- не можна класти більший диск на менший.
Існує легенда, що в індійському місті Бенаресі бог Брама поставив в одному з храмів на бронзовій майданчику три алмазні палички товщиною в корпус бджоли, на одну з них він надів 64 золотих диска, і з моменту створення світу без втоми, змінюючи один одного, жерці переносять диски з однієї палички на іншу відповідно до описаних правилами. Коли жерці перенесуть всі диски з першої палички на третю, - говорить легенда.- настане кінець світу.
Давайте розберемося, як же перенести диски з першого стрижня на третій, а за одне з'ясуємо, чи скоро настане обіцяний кінець світу.
Якби в піраміді був тільки один диск, то рішення очевидно - перенесемо його на третій стрижень, і справа з кінцем. Ми виконали необхідну завдання за один хід. А якби було два диска? Тоді покладемо спочатку менший диск на другий стрижень, потім покладемо другий диск на третій стрижень, потім пренесени і менший диск на третій стрижень, поклавши його поверх другого. Усе. За три дії ми змогли перекласти обидва диска на третій стрижень. Відзначимо, що 1 = 2 ^ 1 - 1, а 3 = 2 ^ 2 - 1. Тепер припустимо, що ми вміємо перекладати на третій стрижень піраміду з n дисків за 2 ^ n-1 дію. Покажемо, що в такому випадку можна перенести на третій стрижень і піраміду з n + 1 дисків, до того ж за 2 ^ (n + 1) - 1 дію.
Дійсно, нехай на піраміді лежить n + 1 дисків. На вромя змінимо нумерацію стрижнів: другий назвемо третім, а третій - другим. Тепер ми можемо перенести n верхніх дисків з першого стрижня на третій, зробивши 2 ^ n - 1 дію. На першому стрижні залишився лише один диск. Перенесемо його на вільний другий стрижень. Знову перенумеруем стрижні: повернемо другого стрижня номер три, першому дамо номер два, а третьому - номер один. Тепер у нас на першому стрижні лежить n дисків, другий - вільний, а на третьому лежить найбільший диск. Залишилося перенести з першого стрижня на третій n дисків, що ми вміємо робити за 2 ^ n - 1 операцію. Усе. Ми зібрали на третьому стрижні все n + 1 дисків, зробивши 2 ^ (n + 1) - 1 дію.
Звідси, відповідно до принципу математичної індукції, випливає, що для будь-якого натурального числа до можна, маючи піраміду з k дисками, перенести їх з першого стрижня на третій, дотримуючись правил, за 2 ^ k - 1 дію.
Наведене доказ неважко оформити у вигляді алгоритму дій. Саме такий алгоритм і пропонується програмістам в згаданих книгах для його записи на тому чи іншому алгоритмічній мові.
Неважко показати, що менше ніж за 2 ^ k - 1 дію перенести k дисків з першого стрижня на третій неможливо. Тому легендарним жерцям знадобиться 2 ^ 64-1 дію, щоб виконати свою роботу. Якщо витрачати на кожну дію лише по одній секунді, то знадобиться 18 446 744 073 709 551 615 с, т. Е. Понад 500 мільярдів років.
Придивімося уважніше до процесу перенесення дисків. Для цього перенумеруем їх в порядку зростання: перший - найменший і т. Д. Тепер почнемо переносити диски відповідно до алгоритму і будемо записувати номера переносяться дисків:
Цікаво, що кожен непарний перенесення - це перенесення першого диска. Ще одне спостереження: розташуємо стрижні в вершинах рівностороннього трикутника і поспостерігаємо за рухом першого диска. Виявляється, що він рухається по колу в одну і ту ж сторону; при цьому, якщо початкова кількість дисків парне, то за годинниковою стрілкою, а якщо непарне - проти. Ці спостереження дозволили в 1961 році сформулювати наступний алгоритм перенесення дисків:
спочатку переносимо перший диск, потім не перший, потім знову перший, потім не перший і т. д. причому перший диск переноситься в одному напрямку: за годинниковою стрілкою в разі парного кількості дисків і проти годинникової стрілки, в разі їх непарної кількості.
Зауважимо, що вказівка «переноситься не перший диск» повністю визначає, який диск і куди слід переносити в даний момент, оскільки менший диск завжди кладеться на більший.
Нещодавно школяр з м Пермі Миша Федоров запропонував ще один алгоритм, який здійснює, як і тільки що описаний, перенесення k дисків з першого стрижня на третій за 2 ^ k - 1 дію.
Миша вводить поняття «порожній вежі». Стрижні з нанизаними на них дисками він називає вежами, а вежу, яка не бере участі в операції перенесення диска в цей момент, називає порожній. Алгоритм М. Федорова формулюється дуже коротко:
в процесі перекладання порожня вежа повинна рухатися по колу в одному і тому ж напрямку: за годинниковою стрілкою, якщо число дисків непарній, і проти годинникової стрілки, якщо їх число парне.
Свою роботу Миша Федоров з успіхом доповів на Всесоюзній науково-технічній конференції школярів. Зауважимо, що якщо перший алгоритм призводить до необхідного результату з побудови, то справедливість другого і третього слід доводити, і це не дуже просто. Хоча насправді все три алгоритму є просто різними записами одного і того ж процесу перенесення дисків.
Істотно інший процес виникає в тому випадку, якщо ще ускладнити правила перенесення. Наш читач А. Тарасенко пропонує знайти алгоритм, що дозволяє переносити диски з першого стрижня на третій, в якому перший диск жодного разу не опинявся б на другому стрижні. Він стверджує, що така процедура можлива за 2 * 3 ^ (k-1) - 1 дію. І взагалі, якщо заборонити другого диску надаватися на другому стрижні, то кількість перекладань стає рівним 2 ^ 2 * 3 ^ (k-2) -1. І взагалі, якщо заборонити класти на другий стрижень n-й диск, то знадобиться 2 ^ n * 3 ^ (k-n) -1 дію.
Ще про одну модифікації цієї головоломки ми писали в попередньому номері журналу (на 4 сторінці обкладинки). В. Панаєв пропонує розглянути питання: чи завжди можливо перенести диски з першого стрижня на третій, якщо спочатку вони лежали на першому стрижні в довільному порядку. Наводимо доказ того, що таке перекладання завжди можливо.
Щоб довести можливість такого перекладання, спочатку розберемося з більш простим завданням. Нехай потрібно зібрати піраміду з дисків, нанизаних на два стрижня, при вільному третьому, причому диски розташовані на стрижнях по зростанню діаметрів. Крім того, припустимо, що таке завдання ми вже вміємо вирішувати для будь-якого меншої кількості дисків.
Нехай найбільший диск знаходиться на першому стрижні, тоді щоб зібрати піраміду на третьому стрижні, необхідно зробити три операції:
- зібрати на другому стрижні піраміду без найбільшого диска;
- перемістити найбільший диск на третій стрижень;
- перемістити піраміду з другого стрижня на третій.