Ханойская башня

Ханойская башня

Приготовьте дощечку и укрепите в ней три палочки. Затем приступите к изготовлению башенки. Она должна состоять из восьми фанерных кружков. Самый большой — внизу (его диаметр 65 мм); каждый следующий в диаметре меньше предыдущего на 5 мм. Все кружки желательно окрасить в различные цвета.

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

Начинать следует с небольшого числа кружков (4, 5) и затем постепенно прибавлять по одному. Игра эта не так проста, как может показаться. Чтобы переложить четыре кружка, нужно сделать не менее 15 перекладываний; при пяти — 31; при шести—63; при семи — 127; при восьми — 255. Если бы кружков было 64, то чтобы переложить их, соблюдая наши правила, пришлось бы сделать 18 446 744 073 709 551 616 перекладываний, на что потребовалось бы не менее 500 миллиардов лет.

Минимальное количество перекладываний легко определить по формуле 2Т —1, где Т — количество кружков в пирамиде.