Упр.516 ГДЗ Никольский Потапов 9 класс (Алгебра)

Задача

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

Подробный ответ

Обозначим через $$T_n$$ наименьшее число ходов, необходимое для переноса $$n$$ колец.

При $$n=1$$ имеем:

$$T_1=1=2^1-1.$$

Пусть для некоторого $$n=k$$ верно:

$$T_k=2^k-1.$$

Докажем формулу для $$n=k+1$$. Чтобы перенести $$k+1$$ колец, нужно:

перенести верхние $$k$$ колец на вспомогательный штырёк — это займёт $$T_k$$ ходов;
перенести самое большое кольцо на другой штырёк — $$1$$ ход;
перенести $$k$$ колец со вспомогательного штырька на нужный — ещё $$T_k$$ ходов.

Значит,

$$T_{k+1}=T_k+1+T_k=2T_k+1.$$

Подставим сюда $$T_k=2^k-1$$:

$$ T_{k+1}=2(2^k-1)+1=2^{k+1}-2+1=2^{k+1}-1. $$

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

$$T_n=2^n-1.$$