green_fr | Pour la science № 457 — Ханойские башни

С детства помню имя Эдуарда Лукаса, изобретателя разных математических головоломок, в том числе Ханойской башни. Оказывается — он Лука, француз. Краткая биография в журнале — перечисление великих людей, с которыми он дружил или работал, затем «во время банкета официант разбил тарелку, осколком поцарапал голову Лукасу, от заражения тот скончался». Отличная смерть...

Статья про Ханойские башни. Я был уверен, что там и задача единственная (переставить все диски с одного столбика на другой), и решение единственное (переставить n дисков = переставить в сторону n-1, переставить самый большой, переставить отставленные n-1). Оказывается, задач можно сформулировать огромное количество — начальная и конечная позиции не обязаны быть одинаковыми «все диски на одном шесте». А решение мало того, что не единственное, оно даже не всегда единственное оптимальное (есть задачи со множественными оптимальными решениями).

Плюс, можно экспериментировать с количеством шестов — задача оптимального алгоритма с 4 шестами решена, для большего количества шестов — пока нет.

С тремя шестами можно легко нарисовать граф всех возможных состояний. Для этого используют нотацию типа BBAC — первый (самый большой) диск находится на шесте B, второй тоже, третий на A, четвёртый на C (этой информации достаточно для нахождения единственного возможного расположения дисков на каждом шесте). В таких «координатах» граф возможных состояний со всеми возможными переходами (если увеличивать до бесконечности количество дисков) представляет собой треугольник Серпинского.

Для 4 шестов граф, очевидно, не плоский — интересно было бы попытаться нарисовать его в 3D, покрутить на экране. Кстати, как моделируются подобные вещи? Я сначала думал накидать точки в случайном порядке, связать их гранями с какой-то «жёсткостью» и отпустить (моделировать, как они будут притягиваться / отталкиваться), пока они не найдут какое-то равновесное состояние. Но, почему-то, кажется лажей, наверняка должны быть какие-то более разумные методы.

Продолжая играть с графом на треугольнике Серпинского — если взять стандартную задачу «переложить все диски с шеста A на шест C», но при этом запретить прямой перенос дисков между шестами A и C, то решение мало того, что существует (мне это было совершенно не очевидно!), так его графическое отображение ещё и осуществляет проход по всем точкам графа (по всем возможным состояниям Ханойских башен).

А ещё, люди заинтересовались средней сложностью задачи о башнях из n дисков. То есть, случайное начальное состояние, случайное конечное, какое среднее количество ходов необходимо для перехода из одного в другое. Понятно, что задача сводится к среднему расстоянию между точками треугольника Серпинского. Интуитивно кажется, что там должна быть иррациональная красота, вроде размерности самого треугольника (ln(3) / ln(2)). Но нет, среднее расстояние оказалось рациональным числом — 466/885 (в треугольнике с длиной стороны, принятой за 1). Откуда оно вылезло — совершенно непонятно!