Даны три стержня, на один из которых нанизаны $%n$% колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее. Найти наименьшее число ходов.

Я доказал по индукции, что это возможно сделать за $%2^{n - 1}$% шагов. Однако как теперь доказать, что это кол-во минимально?

задан 28 Дек '14 20:56

изменен 30 Дек '14 14:29

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

Это доказывается по индукции. При $%n=1$% нужен один ход для переноса кольца на другой стержень. Пусть $%n > 1$%, и для меньшего числа колец утверждение о минимальности считается доказанным. В какой-то момент мы должны перенести самое большое (нижнее) кольцо на другой стержень. Он при этом должен быть свободен, а остальные кольца лежат в нужном порядке на третьем стержне. Чтобы их туда перенести (не трогая самое нижнее кольцо), нужно как минимум $%2^{n-1}-1$% ходов по предположению индукции.

Теперь переносим большое кольцо на второй стержень, и далее возникает задача переноса на него всех колец с третьего стержня. Если предположить, что самое большое кольцо мы далее не трогаем, то такая операция требует не менее $%2^{n-1}-1$% ходов -- опять же, по предположению индукции. Общее число ходов при этом равно $%(2^{n-1}-1)+1+(2^{n-1}-1)=2^n-1$%.

Логически возможен вариант,что мы действуем как-то по-другому, то есть делаем какие-то ещё преобразования. Однако, если самое большое кольцо мы куда-то переносим, то настанет момент, когда это делается в последний раз. При этом тот стержень, на который мы его переносим, должен быть свободен, и тогда другие $%n-1$% колец лежат в допустимом порядке на оставшемся стержне. Это значит, что мы всё равно вернёмся к только что разобранной ситуации, и общее число ходов при отклонении от стандартного способа переноса только увеличится.

ссылка

отвечен 28 Дек '14 21:48

@falcao: Если в условии задачи увеличить количество стержней до четырёх, то задача будет существенно интереснее.

(29 Дек '14 3:11) EdwardTurJ

@EdwardTurJ: да, это интересный вариант. Не знаю, рассматривал ли я когда-нибудь такого рода задачу (или что-то похожее на неё).

(29 Дек '14 3:34) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×85
×33

задан
28 Дек '14 20:56

показан
1817 раз

обновлен
29 Дек '14 3:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru