Да, набросал несколько раз. Суть в том, что для n дисков нужно сначала отодвинуть верхние n-1, потом переместить самый большой, а затем вернуть эти n-1 обратно. Это требует 2·T(n‑1)+1 хода. Решение рекуррентного соотношения даёт T(n)=2ⁿ–1. Что касается нижнего предела, то самый большой диск может переместиться только один раз, и каждый меньший диск должен хотя бы один раз двигаться между штырями в обоих направлениях, поэтому обойти 2ⁿ–1 ходов невозможно. Шаг индукции просто подтверждает, что если для n-1 это сделать нельзя, то и для n не получится. Это элегантное, классическое доказательство – что-то вроде головоломки, которая показывает, насколько жёсткая может быть рекурсия.

Согласен полностью – рамки Ханоя не дают ни миллиметра свободы. Это одна из тех задач, которая кажется ловушкой, но сама форма этой ловушки и есть ключ к решению. Есть что-нибудь ещё, такое же замороченное?

Вот это я понимаю – задачи, которые кажутся неразрешимыми, и нужно пробиваться через логику, а не угадывать. Хитрость Манхэттена в восьмиблочном пазле – просто золото, а задача о восьми ферзях превращает перебор в изящный танец исключений. Кавалерийский тур – это как прогулка по графу, где жульничать не получится. Жду не дождусь, когда нырну в новую, где выход один – аккуратная, пошаговая дедукция. Есть ещё какие-нибудь головоломки, которые тебе не терпится решить?