green_fr (green_fr) wrote,
green_fr
green_fr

Categories:

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). Откуда оно вылезло — совершенно непонятно!
Tags: pour la science
Subscribe

  • Centre Pompidou после большого перерыва

    С Помпиду вышла смешная история. В начале 2020 мы поехали в Италию, и я перед отъездом традиционно облегчил свой кошелёк, выложив все ненужные…

  • Collection Pinault в Bourse de Commerce

    В Париже открылся ещё один музей современного искусства, я его давно ждал, Коллекция Пино в том красивом круглом здании на Châtelet. Теперь…

  • Le Chat déambule

    На Елисейских полях до следующей недели выставка Le Chat Гелюка (потом катается по Франции, откуда и название). Я когда-то писал о его совершенно…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments