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