Комбинаторика на Турломе: графы, игры, клетчатые задачи, Дирихле
Ошибка.
Попробуйте повторить позже
У Ярослава есть 
замков, пронумерованных числами от 1 до 
расположенных по кругу в порядке увеличения номеров от 1 до 
по
часовой стрелке. В начальный момент времени все замки открыты. Ярослав начинает с замка с номером 1 и движется всегда по часовой
стрелке. Если Ярослав находится у замка с номером 
то:
- если открытых замков сейчас суммарно больше
то Ярослав закрывает следующие по часовой стрелке 
открытых замков,
и переходит к следующему после этого открытому замку (возможно, снова к замку с номером 
);
- если открытых замков сейчас суммарно не больше
то Ярослав закрывает все замки, кроме замка с номером 
и
заканчивает (таким образом, остаётся открытым только замок с номером 
).
При каком наименьшем 
Ярослав оставит в конце открытым замок с номером 1?
Источники:
Подсказка 1
Попробуйте посмотреть, какие замки точно останутся закрытыми, а какие открытыми, когда Ярослав сделал какое-то кол-во шагов, но всё ещё на первом круге.
Подсказка 2
Мы понимаем, что 1,3,7,15,31,63,127,255,511,1023 будут открыты. Посмотрите, что происходит в моменте, когда Ярослав стоит на 1023 замке, возможно, мы сможем получить оценку на N? Обратите внимание на то, что после замка с номером k он либо остаётся на нём же, либо переходит в замок с номером 2k+1.
Подсказка 3
Да, если N < 2046, то он гарантированно закроет замок с номером 1, а что будет при N = 2046? В этой задаче хорошо, что пример придумывать не нужно, а можно просто проверить, выполняется ли условие после проделанного алгоритма или нет.
Легко видеть, что Ярослав будет находится вначале у замка 
потом — 
Если 
то следующим действием Ярослав закроет замки с номерами 
и, возможно, ещё какие-то. В любом
случае, замок под номером 
останется закрытым.
Если 
то дальше Ярослав закроет все замки с номерами от 
до 
и вновь встанет у замка с номером 
Сейчас
открыты замки 
Дальше Ярослав закрывает замок 
и переходит к замку 
потом закрывает замки
и переходит к замку 
который и оставляет открытым.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
