Давайте на время забудем о САИНТе и перенесемся в Париж 1833 года. Весь город увлечен головоломкой, недавно привезенной из Индокитая. "Ханойская башня"- так называется головоломка. Внешне она выглядела очень просто - небольшая, тщательно отполированная дощечка с тремя стержнями и несколько колец. Правила тоже несложны.
В начале игры все кольца нанизываются на ближний стержень (будем играть с четырьмя кольцами). Они лежат пирамидой - самое большое внизу, самое малое сверху. Нужно побыстрее переложить кольца на дальний стержень, сохранив их порядок. Перекладывать по два кольца сразу нельзя, только по одному. А нанизывать их можно на любой из стержней. Можно и возвратить кольцо на стержень, с которого оно было снято. Запрещено класть большее кольцо на меньшее - на любом стержне кольца всегда складываются в пирамиду.
Первый ход в игре очевиден: переносим маленькое колечко либо на средний, либо на дальний стержень. Пусть мы выбрали средний стержень.
Тогда возникают три возможности: вернуть колечко обратно, перенести его на дальний стержень и вовсе не трогать, а взять следующее кольцо и нанизать его на дальний стержень.
Каждая из возможностей, определившихся после первого хода, в свою очередь, вызывает три варианта развития игры. Если нарисовать этот процесс размножения возможностей в виде дерева, то из корня его берут начало два ствола, от каждого из стволов отходят три ветви, а от каждой ветви - опять три ветви и так далее...
Для решения задачи не все ветви равноценны. Двигаясь по одним, мы долго будем плутать в пышной кроне дерева, а оказавшись на других, быстро достигнем цели. Самый короткий путь включает пятнадцать ветвей; пробираясь по ним, мы приходим к решению - четыре кольца аккуратной пирамидой лежат на дальнем стержне.
Если удалось одолеть головоломку с четырьмя кольцами (это удается не сразу), то можно усложнить задачу и взять восемь колец; при этом кратчайший путь составит 255 шагов. Шестнадцать колец; кратчайший путь - 65 535 шагов...
Большую роль в популярности головоломки "Ханойская башня" сыграла ее связь со старинной индийской легендой о храме города Бенареса. Башня этого храма, гласила легенда, особая. Она сложена из 64 золотых колец, надетых на общий стержень. Рядом вкопаны еще два стержня, и монахи неустанно перекладывают кольца со стержня на стержень, соблюдая особый ритуал. Когда все кольца окажутся на дальнем стержне, грянет гром, храм обратится в пыль, а мир исчезнет.
