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

1.3*. Метод математической индукции. § 1. Действительные числа. Глава I. Корни, степени, логарифмы - номер 1.45, страница 22.

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

Данная задача известна как головоломка «Ханойская башня». Для доказательства того, что наименьшее число ходов, необходимое для переноса 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$.

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

Рассмотрим задачу для $n = k+1$ колец. Нам нужно доказать, что $H(k+1) = 2^{k+1} - 1$.

Чтобы переместить самое большое, $(k+1)$-е кольцо, с исходного штырька (назовем его A) на целевой (C), необходимо, чтобы все остальные $k$ колец, которые меньше него, находились на третьем, вспомогательном штырьке (B). Это ключевое и необходимое условие, так как самое большое кольцо не может быть перемещено, если на нем есть другие кольца, и оно не может быть помещено на штырек, где уже есть меньшие кольца.

Следовательно, любой алгоритм, решающий задачу за минимальное число ходов, должен состоять из следующих этапов:

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

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

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

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

Ответ: Утверждение, что наименьшее число ходов равно $2^n - 1$, доказано методом математической индукции.