Всесиб 2024, 11 класс, задача 5
( баллов) У вредного Васи есть клетчатая полоска длины клеток и лента длины клеток. Вася хочет разрезать свою полоску на несколько кусочков, каждый из которых имеет длину из нескольких целых клеток по своему усмотрению, а затем уложить часть из них на ленту в некотором порядке так, чтобы в какой-то момент осталось не менее одного кусочка, ни один из которых уложить уже нельзя. При этом кусочки укладываются строго по клеткам и не могут выходить за пределы ленты, ни одна клетка не должна быть накрыта ими дважды и, если на ленте есть место, куда можно уложить очередной кусочек, Вася должен уложить его в одно из таких мест по своему выбору. При каком минимальном , как бы Вася ни старался, ему не удастся задуманное, то есть придётся уложить все кусочки?
Ответ
Ответ. .
Решение. Предположим, что Васе удалось задуманное. Обозначим общую длину уже уложенных кусочков за , тогда длина оставшихся равна . Уже уложенные кусочки разбивают ленту максимум на пустых отрезков, длина каждого не превосходит , иначе один из оставшихся кусочков можно было бы уложить. Поэтому . Значит, при всех Васе придётся уложить все кусочки.
Для всех Вася может разрезать полоску на шесть кусочков длины и один кусок длины , затем укладывать единичные кусочки на клетки считая от левого края ленты. После этого оставшийся кусок длины уложить уже нельзя. Следовательно, минимальное значение, при котором Васе не удастся задуманное, равно .
Замечание. Можно сказать, что, если для некоторого при любом разбиении полоски на кусочки Васе всегда придётся уложить все кусочки на ленту длины , то тем более ему придётся уложить все кусочки и на ленту большей длины , поэтому достаточно построить пример для . Однако это кажущееся очевидным утверждение тоже нужно обосновать. Например, рассмотрим произвольное разбиение полоски длины на кусочки, которое нельзя в некотором порядке уложить на ленту длины , но, по предположению, все эти кусочки в том же порядке можно уложить на ленту длины . Воспроизведём схему «не укладки» этих кусочков для большой ленты на маленькой: кусочки будем укладывать в том же порядке на те же клетки маленькой ленты, куда клали на большой. Если часть очередного кусочка или весь он уже не поместятся на маленькой ленте, отрежем их и переместим в конец очереди укладки. Свободные интервалы на маленькой ленте при этом будут такими же, как в исходной схеме «не укладки» на большой; последующие укладки только уменьшают длины свободных интервалов. Поэтому кусочек, который нельзя было уложить на большую ленту, нельзя будет уложить и на маленькую.
Другое доказательство оценки . Предположим, что Васе удалось задуманное. Пусть первый кусочек, который удалось не уложить на ленту, содержал клеток. Разрежем все уже уложенные кусочки на единичные клетки и сдвинем их вправо так, чтобы они оказались на клетках ленты, номера которых, слева направо, делятся на . После этого кусочки-клетки разбивают ленту на отрезки длины , считая самый левый, а правый может быть и меньше. Всё, что с ленты при этом свалилось, и то, что ещё не было уложено, объединим в один большой кусок новой длины , который уложить нельзя. Если , повторим эту процедуру с заменой на до тех пор, пока на очередном шаге не совпадёт с . Значит, если есть некоторая схема «не укладки» полоски длины на ленту длины , то есть и схема, в которой все кусочки, кроме последнего, имеют длину , а последний - длину , и кусочки-клетки разбивают ленту на свободные отрезки длины , кроме самого правого, длина которого не превосходит . Длина ленты в таком случае не превосходит .