6. В основе эффективного решения головоломки «Ханойская башня» лежит алгоритм, суть которого состоит в следующем: для перемещения башни, состоящей из n колец, с первого стержня на третий необходимо решить задачу для n − 1 колец: сначала переместить их на второй стержень, затем переместить самое большое кольцо на третий стержень и повторно переместить n − 1 колец с первого стержня на третий. Таким образом, число ходов для перемещения башни из n колец равно удвоенному числу ходов для перемещения башни из n − 1 колец, равному одному ходу. Используйте эту закономерность для вычисления количества ходов, необходимых для перемещения башни из 64 колец. Вычислите, сколько времени займёт такое перемещение, если считать, что на один ход требуется 1 секунда.

Обозначим через \(H_n\) количество ходов для башни из \(n\) колец. По условию, чтобы переместить башню из \(n\) колец, нужно переместить меньшие кольца, сделать ход самым большим кольцом и снова переместить меньшие кольца: \(H_n=2H_{n-1}+1\), причём \(H_1=1\).

Последовательно удваивая число ходов и прибавляя 1, получаем формулу \(H_n=2^n-1\). Тогда для 64 колец: \(H_{64}=2^{64}-1=18\,446\,744\,073\,709\,551\,615\) ходов.

При одном ходе в секунду это столько же секунд. В годах, считая 365 дней в году: \(\frac{18\,446\,744\,073\,709\,551\,615}{31\,536\,000}\approx584\,942\,417\,355\) лет.

Ответ: 18 446 744 073 709 551 615 ходов; примерно 584,9 миллиарда лет.