Перекладывание монет
Живая математика (Перельман)
В детстве старший брат показал мне, помню. занимательную игру с монетами. Поставив рядом три блюдца, он положил в крайнее блюдце стопку из 5 монет: вниз рублёвую, на неё — 50-копеечную монету, выше — 20-копеечную, далее 15-копеечную и на самый верх — 10-копеечную.
http://vsemmorpg.ru/flash-igry-onlajn/khanoiskaya-bashnya (Играть?)
Нужно перенести эти монеты на третье блюдце, соблюдая следующие три правила. Первое правило: за один раз перекладывать только одну монету. Второе: никогда не класть большей монеты на меньшую. Третье: можно временно класть монеты и на среднюю тарелку, соблюдая оба правила, но к концу игры все монеты должны очутиться на третьем блюдце в первоначальном порядке. Правила, как видишь, не сложные. А теперь приступай к делу.
Я принялся перекладывать. Положил 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×2-1 |
| 7 | = | 2×2×2-1 |
| 15 | = | 2×2×2×2-1 |
| 31 | = | 2×2×2×2×2-1. |
— Понимаю: сколько монет перекладывается, столько раз берётся двойка множителем, а затем отнимается единица. Я мог бы теперь вычислить число ходов для любой стопки монет. Например, для 7 монет:
— Вот ты и постиг эту старинную игру. Одно только практическое правило надо тебе ещё знать: если в стопке число монет нечётное, то первую монету перекладывают на третье блюдце; если чётное — то на среднее блюдце.
— Ты сказал: старинная игра. Разве не сам ты её придумал?
— Нет, я только применил её к монетам. Игра очень древнего происхождения и зародилась, говорят, в Индии. Существует интересная легенда, связанная с этой игрой. В городе Бенаресе будто бы имеется храм, в котором индусский бог Брама при сотворении мира установил три алмазные палочки и надел на одну из них 64 золотых кружка: самый большой внизу, а каждый следующий меньше предыдущего. Жрецы храма обязаны без устали, днем и ночью, перекладывать эти кружки с одной палочки на другую, пользуясь третьей, как вспомогательной, и соблюдая правила нашей игры; переносить за один раз только один кружок и не класть большего на меньший. Легенда говорит, что когда будут перенесены все 64 кружка, наступит конец мира.
