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