Ханойські вежі з чотирьма стержнями

Зверніться до опису класичної задачі про Ханойські вежі з трьома стержнями.

У цій задачі ми розширимо задачу про Ханойські вежі на чотири стержні і поставимо питання: "Яка мінімальна кількість переміщень потрібна для вирішення задачі про Ханойські вежі для заданого $n$, якщо у нас чотири стержні замість трьох?" Зберігаються правила: необхідно перекладати $n$ дисків з одного заданого стержня на інший, не дозволяється ставити більший диск на менший. Головна відмінність — тепер для допоміжних стержнів є два замість одного.

Наприклад, щоб перемістити $3$ диски зі стержня $A$ на $D$, можна виконати такі кроки: диск $1$ з $A$ на $B$, диск $2$ з $A$ на $C$, диск $3$ з $A$ на $D$, диск $2$ з $C$ на $D$, диск $1$ з $B$ на $D$, разом $5$ переміщень.