Номер 727, страница 162 - гдз по математике 5 класс учебник Никольский, Потапов

727. Головоломка. Имеется 3 штырька, на один из которых насажены 3 кольца (рис. 154). За сколько ходов можно перенести пирамиду из этих трёх колец на другой штырёк, если за один ход разрешается переносить только одно кольцо; при этом нельзя большее кольцо класть на меньшее. Решите задачу:

a) для четырёх колец;

б) для пяти колец.

Рис. 154

Это классическая задача-головоломка, известная как «Ханойская башня». Цель состоит в том, чтобы переместить все кольца с одного штырька на другой, соблюдая два правила: можно перемещать только одно кольцо за раз и нельзя класть большее кольцо на меньшее.

Минимальное количество ходов, необходимое для перемещения $n$ колец, можно найти по формуле: $M_n = 2^n - 1$.

Давайте разберемся, откуда берется эта формула. Пусть $M_n$ — минимальное количество ходов для $n$ колец. Чтобы переместить башню из $n$ колец со штырька A на штырёк C, используя штырек B как вспомогательный, необходимо выполнить следующие действия:

1. Переместить верхние $n-1$ колец со штырька A на вспомогательный штырёк B. Для этого потребуется $M_{n-1}$ ходов.
2. Переместить самое большое, $n$-ое кольцо, со штырька A на целевой штырёк C. Это займёт 1 ход.
3. Переместить $n-1$ колец со вспомогательного штырька B на целевой штырёк C. Для этого снова потребуется $M_{n-1}$ ходов.

Таким образом, мы получаем рекуррентное соотношение: $M_n = M_{n-1} + 1 + M_{n-1} = 2M_{n-1} + 1$.

Зная, что для одного кольца ($n=1$) требуется 1 ход ($M_1=1$), можно последовательно найти количество ходов для любого числа колец:

• $M_1 = 1$
• $M_2 = 2 \cdot M_1 + 1 = 2 \cdot 1 + 1 = 3$
• $M_3 = 2 \cdot M_2 + 1 = 2 \cdot 3 + 1 = 7$

Решение этого рекуррентного соотношения приводит к общей формуле $M_n = 2^n - 1$. Теперь применим ее для решения задачи.

Для перемещения пирамиды из четырёх колец ($n=4$), подставим это значение в нашу формулу.

Количество ходов $M_4 = 2^4 - 1 = 16 - 1 = 15$.

Можно также рассуждать пошагово, используя результат для трех колец ($M_3=7$):

1. Переместить башню из 3-х верхних колец на вспомогательный штырёк. Это займёт 7 ходов.
2. Переместить самое большое, 4-е кольцо, на целевой штырёк. Это 1 ход.
3. Переместить башню из 3-х колец со вспомогательного штырька на целевой, поверх самого большого. Это займёт ещё 7 ходов.

Итого: $7 + 1 + 7 = 15$ ходов.

Ответ: 15 ходов.

Для перемещения пирамиды из пяти колец ($n=5$), действуем аналогично.

Количество ходов $M_5 = 2^5 - 1 = 32 - 1 = 31$.

Или пошагово, используя результат для четырех колец ($M_4=15$):

1. Переместить башню из 4-х верхних колец на вспомогательный штырёк. Это займёт 15 ходов.
2. Переместить самое большое, 5-е кольцо, на целевой штырёк. Это 1 ход.
3. Переместить башню из 4-х колец со вспомогательного штырька на целевой. Это займёт ещё 15 ходов.

Итого: $15 + 1 + 15 = 31$ ход.

Ответ: 31 ход.