Склад представляет собой прямоугольный параллелепипед с целыми сторонами, контейнеры — прямоугольные параллелепипеды с размерами 1× 1× 3 м. Контейнеры на складе можно класть как угодно, но параллельно границам склада.
а) Может ли оказаться, что полностью заполнить склад размером 120 кубометров нельзя?
б) Может ли оказаться, что на склад объемом 100 кубометров не удастся поместить 33 контейнера?
в) Пусть объем склада равен 800 кубометрам. Какой процент объема такого склада удастся гарантированно заполнить контейнерами при любой конфигурации склада?
Решение:
а) Стороны склада — целые числа, и его объем 120 делится на 3, поэтому есть сторона, длина которой кратна 3. Обозначим ее длину через . Тогда выложим контейнеров с размерами м длинной стороной вдоль стены с длиной . Длины остальных сторон склада делятся на длины других сторон контейнеров, так как любое целое число делится на 1. Тогда аналогичным образом продолжим выкладывать контейнеры и заполним такими операциями весь склад. Значит, склад размером 120 кубометров точно можно заполнить данными контейнерами.
б) Попробуем построить пример. Для того чтобы не пришлось рассматривать много случаев, возьмем такой склад, в который можно поместить контейнеры только одним способом. То есть все стороны должны быть меньше 6. Если возьмем склад размером м, то сторона длины 3 м любого из уложенных контейнеров должна быть параллельна стороне длины 25 м склада. Мысленно разделим склад на четыре полосы размерами . В каждую из них можно поместить не более 8 контейнеров. Возможно, некоторые контейнеры будут лежать в нескольких полосах одновременно. Но в любом случае максимальное количество уникальных контейнеров, которые можно разместить на складе , равно . Значит, поместить 33 контейнера не удается.
в) Рассмотрим склад размером . Вдоль стен со сторонами 2 м не получится класть контейнеры стороной 3 м, значит, сторона 3 м у контейнера будет лежать вдоль стены 200 м. То есть по соображениям из пункта б) на такой склад поместится максимум контейнера. Тогда останется свободным хотя бы
кубометров объема, то есть 1% склада. Значит, более чем 99% объема склада гарантированно заполнить не удастся.
Теперь докажем, что хотя бы 99% объема при любой другой конфигурации склада заполнить получится. Пусть дан склад размером и сторона . Тогда можем мысленно отделить часть склада со стороной 3 м и останется объем , а часть склада можно полностью заполнить контейнерами с помощью алгоритма из пункта а). Такую операцию можно делать с любой стороной склада, длина которой не меньше 3. Тогда будем продолжать отрезать части склада со стороной 3 м до тех пор, пока не останется параллелепипед с измерениями, не превосходящими . Получим, что пустует максимум 8 кубометров из 800, то есть максимум 1%. Таким образом, хотя бы 99% объема при любой конфигурации склада получится заполнить.
Ответ: а) Нет б) Да в) 99%