Ханойская башня

Источник

Ханойская башня - популярная в XIX веке головоломка, которую изобрёл французский математик Эдуард Люка. В оригинале она представляет собой три стержня, на один из которых нанизано восемь колец. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее. Задача, на самом деле, не самая сложная, если речь идёт о восьми кольцах и трёх стержнях, но если количество стержней и колец увеличивать, то начинается шиздец. Там уже было поле сражения, где бились учёные-математики, вырабатывая оптимальные стратегии и определяя количество ходов, необходимых для решения головоломки с тысячей дисков и десятью стержнями. В итоге, в 1941 году был разработан алгоритм Фрейма-Стюарта, последовательно проверенный на тридцати дисках и четырёх стержнях. Дальше никто копать не стал, так как этого было достаточно для подтверждения оптимальности алгоритма. Это окончательно подтвердили в 2014 году. Но речь шла о четырёх стержнях. Алгоритма для тысячи колец и десяти стержней не существует до сих пор.