Как выглядит граф состояний Ханойских башен?

[stzozo]

Кто правильно ответит - получит вторую часть задачи.

Comments

[jora0]

А что значит "как выглядит"? Думаю, его можно нарисовать в виде сетки, растянутой между 3-мя "главными" вершинами, причём симметричной относительно как поворотов на 120 градусов, так и отражений вокруг осей, проходящих через главные вершины. К каждой из главных вершин сходятся 2 ребра, к прочим --- 3. В сетке при этом будут наблюдаться различного размера "дыры", и мне кажется, при достаточно большом числе шайб в башнях это всё будет сильно напоминать фрактал.

[stzozo]

Да, фрактал.
И у этого фрактала есть название.

[jora0]

Салфетка Серпинского же! Причём доказывается элементарно по индукции --- для одной шайбы, очевидно, треугольник, пусть для n шайб тоже треугольник, тогда при добавлении одной шайбы 2 бывшие главные вершины становятся не главными, но оказываются связанными с аналогичными треугольниками. Это легко проиллюстрировать, если записывать состояние как расстановку целых чисел от 1 до n по 3-м позициям. Тогда главные вершины n-шайбовых башен имеют вид
(12...n|0|0), (0|12...n|0) и (0|0|12...n);

при добавлении в 1-ю башню ещё одной шайбы бывшие главные вершины станут иметь вид
(12...n n+1 |0| 0), (n+1|12...n|0) и (n+1|0|12...n);
Очевидно, 1-я так и остается главной, а вторые 2 связаны с
(0|12...n|n+1) и (0|n+1|12...n). Но это --- аналогичные вершины таких же треугольников (будем называть их "главными"), только построенных вокруг третьей и второй башен соответственно.

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