Гарантированная упаковка контейнеров

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Полное заполнение при кратном объёме
  2. Ответ: нет

    Сначала: Полное заполнение при кратном объёме

  3. Склад, достигающий границы

    Сначала: Ответ: нет

  4. Конструкция и точный результат

    Сначала: Склад, достигающий границы

  5. Ответ: да

    Сначала: Конструкция и точный результат

  6. Упаковка с остаточным малым блоком

    Сначала: Ответ: да

  7. Склад, достигающий границы

    Сначала: Упаковка с остаточным малым блоком

  8. Конструкция и точный результат

    Сначала: Склад, достигающий границы

  9. Ответ

    Сначала: Конструкция и точный результат

Разобранный пример

Склад представляет собой прямоугольный параллелепипед с целыми сторонами, контейнеры — прямоугольные параллелепипеды с размерами 1×1×31\times 1\times 3 м. Контейнеры на складе можно класть как угодно, но параллельно границам склада.

а) Может ли оказаться, что полностью заполнить склад размером 120 кубометров нельзя?

б) Может ли оказаться, что на склад объемом 100 кубометров не удастся поместить 33 контейнера?

в) Пусть объем склада равен 800 кубометрам. Какой процент объема такого склада удастся гарантированно заполнить контейнерами при любой конфигурации склада?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Целые длины рёбер имеют произведение, кратное трём. Так как три - простое число, хотя бы одна длина кратна трём. Вдоль этого ребра укладываем контейнеры длины три; по двум другим направлениям они имеют единичную толщину. Весь склад заполняется.
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. Берём склад с двумя рёбрами длины два, а третьим равным четверти объёма. Контейнер длины три не может быть направлен вдоль коротких рёбер. Любую упаковку можно сдвинуть к целым делениям: округляем вниз положение нижней границы каждого контейнера вдоль каждого ребра. Поскольку все длины целые, разделяющее два контейнера неравенство и границы склада сохраняются. Поэтому достаточно упаковок по целым делениям. В них имеются четыре отдельные единичные колонки, в каждую входит floor(длина/3) контейнеров. Это даёт точный предел и контрпример при объёме сто, а при объёме восемьсот доказывает оптимальность гарантированного процента.
Шаг 2. Приводим полученный набор, параметры или распределение.
T=(2;2;25;32)\mathcal T=\left(2;2;25;32\right)
Шаг 3. Да. Приведённая конструкция выполняет все условия.
Шаг 1. По каждой длине отделяем слои толщины три и полностью заполняем их контейнерами, направленными поперёк слоя. Не заполненным остаётся лишь прямоугольный блок, все три длины которого - остатки исходных длин по модулю три, то есть не больше двух. Его объём не больше восьми. Следовательно, из восьмисот кубометров гарантированно заполняются не меньше семисот девяноста двух.
Шаг 2. Берём склад с двумя рёбрами длины два, а третьим равным четверти объёма. Контейнер длины три не может быть направлен вдоль коротких рёбер. Любую упаковку можно сдвинуть к целым делениям: округляем вниз положение нижней границы каждого контейнера вдоль каждого ребра. Поскольку все длины целые, разделяющее два контейнера неравенство и границы склада сохраняются. Поэтому достаточно упаковок по целым делениям. В них имеются четыре отдельные единичные колонки, в каждую входит floor(длина/3) контейнеров. Это даёт точный предел и контрпример при объёме сто, а при объёме восемьсот доказывает оптимальность гарантированного процента.
Шаг 3. Приводим полученный набор, параметры или распределение.
T=(2;2;200;264)\mathcal T=\left(2;2;200;264\right)
Шаг 4. Записываем полученный ответ.
9999

Открыть задачу целиком

Попробовать самостоятельно