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