Башня и треугольник | Игра в науку

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

Хотя польский математик Вацлав Серпинский (1882-1969) наиболее известен своим знаменитым «ковром». Он также разработал и другие фрактальные объекты, такие как треугольник, носящий его имя, который получается следующим образом:

В равностороннем треугольнике (хотя подойдет любой треугольник) соединяем середины сторон и устраняем полученный таким образом центральный треугольник (пустое место на рисунке), оставляя 3 треугольника, площадь соединения которых составляет 3/4 площади исходного треугольника. То же самое проделываем с тремя оставшимися треугольниками, оставив 9 треугольников, площадь соединения которых составляет 9/16 площади исходного треугольника… и так до бесконечности.

Ну, как указывает Танганелли: «График движений Ханойской башни подобен треугольнику Серпинского, и кратчайший путь между двумя крайними положениями (где все диски находятся на одной оси) отображается как одна сторона упомянутого треугольника. “…Я спросил себя, существует ли более длинный путь между двумя крайними положениями, и оказалось, что он есть. Этот путь оказывается гамильтоновым”.

(Уточняю, что граф тривиальной башни с одним диском — это исходный треугольник, граф башни с двумя дисками — это первый шаг процесса Серпинского, то есть треугольник, разделенный на четыре части, и так далее. последовательно ).

Как мы видели, кратчайший путь для башни из n дисков требует 2–1 хода. Сколько ходов требует гамильтонов путь? Оба пути уникальны?

Истинное имя Бога

Говоря о любопытных параллелях, (апокрифическая) легенда о монахах Бенареса, которые непрерывно перемещают 64 золотых диска с башни в Ханое, чья огромная задача, по завершении, будет означать конец света, имеет своего аналога в знаменитом рассказ Артура Кларка под названием Девять миллиардов имен Бога, в котором рассказывается история некоторых тибетских монахов, которые постоянно комбинируют буквы своего алфавита, пытаясь составить истинное имя Бога; Когда они его найдут, делать будет нечего, и звезды погаснут. Принимая во внимание, что тибетский алфавит состоит из тридцати букв, что имя Бога не может состоять более чем из девяти букв и что одна и та же буква не может встречаться более трех раз подряд (так как это привело бы к непроизносимому имени даже для тибетца). монах), неужели число возможных божественных имен действительно порядка миллиардов? Или в данном случае ближе к истине те, кто ошибочно переводит миллиарды в триллионы?

Поставим перед собой несколько более простую задачу, чем задача тибетских монахов: предположим, что тот, кто назвал высшее существо «Богом», правильно угадал количество букв и соотношение гласных и согласных, но не нашел истинного имени. Сколько возможных имен, состоящих из четырех букв, двух гласных и двух согласных, совместимых с морфологией испанского языка? Но не цитируйте их вслух, на всякий случай…

Вы можете следить МАТЕРИЯ в Фейсбук, Икс е Инстаграмиди сюда, чтобы получить наш еженедельный информационный бюллетень.