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

516. На один из трёх штырьков насажены $n$ различных колец так, что большее кольцо лежит ниже меньшего (на рисунке 62 $n = 3$). За один ход разрешается перенести одно кольцо с одного штырька на другой, при этом не разрешается большее кольцо класть на меньшее. Докажите, что наименьшее число ходов, за которое можно перенести все кольца с одного штырька на другой, равно $2^n - 1$.

Рис. 62

Для доказательства того, что наименьшее число ходов, за которое можно перенести все $n$ колец с одного штырька на другой, равно $2^n - 1$, воспользуемся методом математической индукции.

Обозначим через $H(n)$ минимальное число ходов, необходимое для перемещения $n$ колец с одного штырька на другой.

Базис индукции:

Проверим утверждение для $n=1$. Если у нас есть только одно кольцо, то для его переноса на другой штырек потребуется ровно один ход.По формуле получаем: $H(1) = 2^1 - 1 = 2 - 1 = 1$.Утверждение верно для $n=1$.

Индукционное предположение:

Предположим, что для переноса $k$ колец наименьшее число ходов действительно равно $H(k) = 2^k - 1$ для некоторого натурального числа $k \ge 1$.

Индукционный шаг:

Докажем, что утверждение верно для $n = k + 1$, то есть $H(k+1) = 2^{k+1} - 1$.Рассмотрим башню из $k+1$ кольца. Пусть штырьки называются A (исходный), B (вспомогательный) и C (целевой). Чтобы переместить самое большое, $(k+1)$-е кольцо со штырька A на штырек C, необходимо, чтобы на штырьке C не было других колец, и чтобы на штырьке A, кроме самого большого кольца, также не было других колец. Это означает, что все верхние $k$ колец должны быть перемещены на вспомогательный штырек B.

Таким образом, процесс переноса $k+1$ кольца разбивается на три обязательных этапа:

1. Перенести башню из верхних $k$ колец с исходного штырька A на вспомогательный штырек B. Согласно нашему индукционному предположению, минимальное число ходов для этого составляет $H(k) = 2^k - 1$.
2. Перенести самое большое, $(k+1)$-е кольцо, с исходного штырька A на целевой штырек C. Это действие занимает ровно 1 ход.
3. Перенести башню из $k$ колец со вспомогательного штырька B на целевой штырек C, поверх самого большого кольца. Это снова займет $H(k) = 2^k - 1$ ходов.

Следовательно, общее минимальное число ходов для $k+1$ кольца равно сумме ходов на всех этапах:

$H(k+1) = H(k) + 1 + H(k) = 2 \cdot H(k) + 1$

Теперь подставим в это выражение значение $H(k)$ из нашего индукционного предположения:

$H(k+1) = 2 \cdot (2^k - 1) + 1 = 2 \cdot 2^k - 2 + 1 = 2^{k+1} - 1$

Мы получили формулу для $n = k+1$. Таким образом, мы доказали, что если формула верна для $k$, то она верна и для $k+1$.

Заключение:

По принципу математической индукции, формула верна для любого натурального числа $n$.

Ответ: Наименьшее число ходов, необходимое для переноса $n$ колец, составляет $2^n - 1$, что и требовалось доказать.