Ханойська вежа вимагає перенести стос із n дисків зі стрижня-джерела на цільовий стрижень, по одному диску за раз, ніколи не кладучи більший диск на менший.

Рекурсивна ідея

Щоб перенести n дисків з A на C, використовуючи запасний стрижень B:

• Перенести верхні n−1 дисків з A на B (рекурсивно).
• Перенести найбільший диск з A на C.
• Перенести n−1 дисків з B на C (рекурсивно).

Чому 2ⁿ−1 ходів

Кількість ходів задовольняє T(n) = 2·T(n−1) + 1 з T(0) = 0. Розгортання рекурентності дає замкнену форму T(n) = 2ⁿ − 1. Це доведений мінімум — коротшого розв'язку не існує.

Зв'язок із двійковим кодом і кодом Грея

Пронумеруйте ходи 1, 2, 3, … у двійковій системі. На ході k рухається диск, номер якого дорівнює позиції наймолодшого встановленого біта числа k (диск 1 — найменший). Послідовність станів дисків утворює код Грея: кожен хід перевертає рівно один диск, тож сусідні стани відрізняються на одну «цифру», як у відбитому двійковому коді Грея.

Легенда

За легендою про храм, жерці переносять 64 золоті диски; світ скінчиться, коли вони завершать. За один хід на секунду це займе 2⁶⁴ − 1 ≈ 5,85 × 10¹¹ років — набагато довше за вік Всесвіту.

Більше стрижнів (Фрейм–Стюарт)

За 4 чи більше стрижнів оптимальна кількість різко зменшується. Алгоритм Фрейма–Стюарта розбиває стос і гіпотетично оптимальний, але ця симуляція тримає класичне ядро на 3 стрижнях, де 2ⁿ − 1 є точним.