Задачка №66. Перекладывание монет

В детстве старший брат показал мне, помню, занимательную игру с монетами. Поставив рядом три блюдца, он положил в крайнее блюдце стопку из 5 монет: вниз рублевую, на нее — 50-копеечную монету, выше — 20-копеечную, далее 15-копеечную и на самый верх — 10-копеечную.

— Нужно перенести эти монеты на третье блюдце, соблюдая следующие три правила. Первое правило: за один раз перекладывать только одну монету. Второе: никогда не класть большей монеты на меньшую. Третье: можно временно класть монеты и на среднюю тарелку, соблюдая оба правила, но к концу игры все монеты должны очутиться на третьем блюдце в первоначальном порядке. Правила, как видишь, не сложные. А теперь приступай к делу.

Я принялся перекладывать. Положил 10-копеечную монету на третье блюдце, 15-копеечную на среднее и запнулся. Куда положить 20-копеечную? Ведь она крупнее и 10-копеечной и 15-копеечной.

— Ну что же? — выручил меня брат. — Клади 10-копеечную на среднее блюдце, поверх 15-копеечной. Тогда для 20-копеечной освободится третье блюдце.

Я так и сделал. Но дальше — новое затруднение. Куда положить 50-копеечную монету? Впрочем, я скоро догадался; перенес сначала 10-копеечную на первое блюдце, 15-копеечную на третье и затем 10-копеечную тоже на третье. Теперь 50-копеечную монету можно положить на свободное среднее блюдце. Дальше, после длинного ряда перекладываний, мне удалось перенести также рублевую монету с первого блюдца и, наконец, собрать всю кучку монет на третьем блюдце.

— Сколько же ты проделал всех перекладываний? — спросил брат, одобрив мою работу.

— Не считал.

— Давай, сосчитаем. Интересно же знать, каким наименьшим числом ходов можно достигнуть цели. Если бы стопка состояла не из 5, а только из 2 монет — 15-копеечной и 10-копеечной, то сколько понадобилось бы ходов?

— Три: 10-копеечную на среднее блюдце, 15-копеечную — на третье и затем 10-копеечную на третье блюдце.

— Правильно. Прибавим теперь еще монету — 20-копеечую — и сосчитаем, сколькими ходами можно перенести стопку из этих монет. Поступаем так: сначала последовательно переносим меньшие две монеты на среднее блюдце. Для этого нужно, как мы уже знаем, 3 хода. Затем перекладываем 20 копеечную монету на свободное третье блюдце — 1 ход. А тогда переносим обе монеты

Со среднего блюдца тоже на третье — еще 3 хода. Итого всех ходов 3 + 1 + 3 = 7.

— Для четырех монет число ходов позволь мне сосчитать самому. Сначала переношу 3 меньшие монеты на среднее блюдце — 7 ходов; потом 50-копеечную на третье блюдце — 1 ход и затем снова три меньшие монеты на третье блюдце — еще 7 ходов. Итого 7 + 1 + 7 = = 15.

— Отлично. А для пяти монет?

— 15 + 1 + 15 = 31, — сразу сообразил я.

— Ну вот ты и уловил способ вычисления. Но я покажу тебе, как можно его еще упростить. Заметь, что полученные нами числа 3, 7, 15, 31- все представляют собой двойку, умноженную на себя один или несколько раз, но без единицы. Смотри.

И брат написал табличку:

 3 = 2 x 2 - 1 
 7 = 2 x 2 x 2 - 1 
 15 = 2 x 2 x 2 x 2 - 1 
 31 = 2 x 2 x 2 x 2 x 2 - 1.

— Понимаю: сколько монет перекладывается, столько рая берется двойка множителем, а затем отнимается единица. Я мог бы теперь вычислить число ходов для любой стопки монет. Например, для 7 монет:

2 x 2 x 2 x 2 x 2 x 2 x 2 - 1 = 128 - 1 = 127.

— Вот ты и постиг эту старинную игру. Одно только практическое правило надо тебе еще знать: если в стопке число монет нечетное, то первую монету перекладывают на третье блюдце; если четное — то на среднее блюдце.

— Ты сказал: старинная игра. Разве не сам ты ее придумал?

рис. 57. 'жрецы обязаны без устали перекладывать кружки'
Рис. 57. ‘Жрецы обязаны без устали перекладывать кружки’

— Нет, я только применил ее к монетам. Игра очень древнего происхождения и зародилась, говорят, в Индии. Существует интересная легенда, связанная с этой игрой. В городе Бенаресе будто бы имеется храм, в котором индусский бог Брама при сотворении мира установил три алмазные палочки и надел на одну из них 64 золотых кружка: самый большой внизу, а каждый следующий меньше предыдущего. Жрецы храма обязаны без устали, днем и ночью, перекладывать эти кружки с одной палочки на другую, пользуясь третьей, как вспомогательной, и соблюдая правила нашей игры; переносить за один раз только один кружок и не класть большего на меньший. Легенда говорит, что когда будут перенесены все 64 кружка, наступит конец мира.

— О, значит, мир давно уже должен был погибнуть, если верить этому преданию!

— Ты думаешь, кажется, что перенесение 64 кружков не должно отнять много времени?

— Конечно. Делая каждую секунду один ход, можно ведь в час успеть проделать 3600 перенесений.

— Ну и что же?

— А в сутки — около ста тысяч. В десять дней — миллион ходов. Миллионом же ходов можно, я уверен, перенести хоть тысячу кружков.

— Ошибаешься. Чтобы перенести всего 64 кружка, нужно уже круглым счетом 500 миллиардов лет!

— Но почему это? Ведь число ходов равно только произведению 64 двоек без единицы, а это составляет… Погоди, я сейчас перемножу!

— Прекрасно. А пока будешь умножать, я успею сходить по своим делам.

И брат ушел, оставив меня погруженным в выкладки. Я нашел сначала произведение 16 двоек, затем умножил этот результат — 65 536 — сам на себя, а то, что получилось, — снова на себя. Потом не забыл отнять единицу.

У меня получилось такое число:

18446744073709551615*.

* (Читателю уже знакомо это число: оно определяет награду, затребованную изобретателем шахматной игры.)

Брат, значит, был прав…

Вам, вероятно, интересно было бы знать, какими числами в действительности определяется возраст мира. Ученые располагают на этот счет некоторыми, — конечно, лишь приблизительными — данными:

 Солнце существует 5000000000000 лет. 
 Земной шар 3000000000 лет. 
 Жизнь на Земле 1000000000 лет. 
 Человек не менее 500000 лет.