Номер / задача 516 страница 146, 148, ГДЗ по алгебре за 9 класс к учебнику Никольского

Учебник: Просвещение, 2024

Условие: На один из трёх штырьков насажены $n$ различных колец так, что большее кольцо лежит ниже меньшего (на рисунке 62 $n = 3$). За один ход разрешается перенести одно кольцо с одного штырька на другой, при этом не разрешается большее кольцо класть на меньшее. Докажите, что наименьшее число ходов, за которое можно перенести все кольца с одного штырька на другой, равно $2^n - 1$. Формула для суммы бесконечно убывающей геометрической прогрессии была известна П. Ферма (XVII в.). В старорусском юридическом сборнике «Русская правда» (X—XI вв.) содержатся оценки количества зерна, собранного с определённого участка земли за определённое время; некоторые из них предполагают вычисление суммы геометрической прогрессии со знаменателем $\dfrac{3}{2}$. Интересные задачи на прогрессии есть в «Арифметике» Магницкого. Вот одна из таких задач: «Некто продавал коня и просил за него 1000 рублей. Купец сказал, что за коня запрошена слишком большая цена. «Хорошо, — ответил продавец, — если ты говоришь, что конь дорого стоит, то возьми его себе даром, а заплати только за одни гвозди в его подковах. А гвоздей во всякой подкове по 6 штук. И будешь ты мне за них платить таким образом: за первый гвоздь полушку (0,25 копейки), за второй гвоздь заплатишь две полушки, за третий гвоздь — четыре полушки и так далее за все гвозди: за каждый в два раза больше, чем за предыдущий». Купец же, думая, что заплатит намного меньше чем 1000 рублей, согласился. Проторговался ли купец, и если да, то на сколько?»

Решение

Обозначим через наименьшее число ходов, необходимое для переноса колец с одного штырька на другой. Докажем по индукции, что

База индукции. При имеем одно кольцо, которое переносится за один ход. Значит, . Равенство выполняется.

Индукционный переход. Предположим, что равенство верно при , т. е. .

Покажем, что . Для этого нужно установить два факта:

1) Можно перенести кольцо за ходов.

Действуем так:

переносим верхние колец с первого штырька на вспомогательный (по предположению индукции это можно сделать за ходов);
переносим самое большое -е кольцо на целевой штырёк (1 ход);
переносим колец со вспомогательного штырька на целевой (ещё ходов).

Итого:

2) Нельзя перенести кольцо менее чем за ходов.

В процессе переноса всех колец самое большое кольцо должно хотя бы один раз переместиться. Но перед тем как его снять, все колец, лежащих на нём, должны быть перенесены на один (вспомогательный) штырёк — это требует не менее ходов. Затем самое большое кольцо перемещается (1 ход). После этого колец нужно перенести на целевой штырёк — это снова требует не менее ходов.

Значит,

Из пунктов 1 и 2 следует, что , т. е. равенство выполняется для .

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

Номер 516