Один диск за раз.
Целая стратегия в уме.

Ниже — план для четырёх дисков. Твоя игровая доска остаётся как есть.

1. Сначала план для четырёх дисков

   Посмотрим на самый большой диск. Чтобы перенести его с левого стержня сразу на правый, нужно освободить и сам диск, и правый стержень. Значит, три меньших диска сначала собираем на среднем.

   Затем переносим большой диск направо, а меньшую башню — со среднего поверх него. Получились три части: маленькая башня → один большой диск → маленькая башня.

   Для одного диска нужен $1$ ход. Для двух по этому плану: $1+1+1=3$. Для трёх: $3+1+3=7$. Поэтому четыре диска можно перенести за $7+1+7=15$ ходов.

2. Почему быстрее нельзя

   Обозначим $T(n)$ — наименьшее число ходов для переноса башни из $n$ дисков. Одинаковые стержни можно менять ролями: от выбора начала и цели минимум не зависит. Для одного диска $T(1)=1$.

   Возьмём любой успешный маршрут, даже если в нём самый большой диск двигается несколько раз. Перед его первым ходом стержень-источник и стержень назначения должны быть свободны от меньших дисков. Значит, вся меньшая башня уже перенесена с начала на оставшийся стержень — это не менее $T(n-1)$ ходов.

   Сразу после последнего хода большого диска на цель все меньшие снова стоят башней на другом стержне. Теперь их нужно перенести на цель поверх большого — ещё не менее $T(n-1)$ ходов. Между этими двумя частями есть хотя бы один ход большим диском.

   Итак, любой маршрут требует не менее $2T(n-1)+1$ ходов. План из трёх частей ровно столько и тратит. Поэтому $T(n)=2T(n-1)+1$. В частности, для четырёх дисков минимум — $15$.

3. Откуда берётся степень двойки

   Посчитаем несколько минимумов по правилу «удвоить предыдущий и прибавить один».

   Дисков $n$	Ходов $T(n)$	Если прибавить $1$
   $1$	$1$	$2$
   $2$	$3$	$4$
   $3$	$7$	$8$
   $4$	$15$	$16$
   $5$	$31$	$32$

   Последний столбец каждый раз удваивается. Это не случайное совпадение: из полученного правила следует $T(n)+1=2(T(n-1)+1)$.

   Для одного диска величина $T(1)+1$ равна $2$. До башни из $n$ дисков остаётся $n-1$ удвоений, значит $T(n)+1=2^n$. Убираем добавленную единицу: $T(n)=2^n-1$.

4. Башня, которую не закончить за жизнь

   В легенде, сопровождавшей игру, жрецы переносят башню из $64$ золотых дисков. Это история о головоломке, а не исторический факт.

   По нашей формуле требуется $2^{64}-1$ ходов — примерно $1{,}8447\cdot10^{19}$. Даже если делать один ход в секунду без остановок, получим около $585$ миллиардов лет. Для оценки делим число ходов на $60\cdot60\cdot24\cdot365{,}25$ секунд в году. Добавить один диск легко; перенос башни после этого требует примерно вдвое больше ходов.

Легенда в инструкции к игре 1883 года — перевод в архиве William & Mary ↗