Индукция в комбинаторике
Ошибка.
Попробуйте повторить позже
Имеется пирамида с 
кольцами возрастающих размеров на стержне (внизу самое большое) и еще два пустых стержня той же высоты.
Разрешается перекладывать верхнее кольцо с одного стержня на другой, но при этом запрещается класть большее кольцо на меньшее.
(a) Докажите, что можно переложить все кольца с первого стержня на один из пустых стержней. (b) Докажите, что это можно сделать за
перекладывание.
Пусть минимальное число шагов для перемещения башни из 
дисков равно 
Выразим 
через 
Рассмотрим башню из
диска. Разобьём всю процедуру на три этапа.
Этап 
— от начала до первого перемещения нижнего диска. В конце этого этапа стоящая на нижнем диске башня из 
дисков должна
переместиться на один из свободных колышков (колышек, на который следующим шагом должен переместиться нижний диск, должен быть
свободен). Нижний диск в этих перемещениях не участвует, следовательно, для этого необходимо (и достаточно) 
шагов.
Этап 
— от первого до последнего перемещения нижнего диска. Одного шага достаточно: после первого перемещения нижний диск
можно больше не трогать.
Этап 
— после последнего перемещения нижнего диска. В начале этого этапа колышек, с которого перед этим был снят нижний диск,
свободен. Значит, на третьем колышке стоит башня из 
дисков, и ее надо переместить на нижний диск. Для такого перемещения также
нужно 
шагов.
Итак, 
(выше показано, что меньшим числом шагов обойтись нельзя, а такого количества достаточно).
Поскольку 
мы можем последовательно вычислить 
Нетрудно вывести и общую формулу: записав полученное
соотношение в виде 
имеем 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
