Чемодан головоломок

Наверное, вы не раз замечали, что аккуратно сложенные вещи занимают гораздо меньше места, чем расположенные случайным образом, а на их упаковку – размещение оптимальным способом – уходит немало времени. Разумеется, такая проблема оптимизации не осталась без внимания математиков! Существует целый класс так называемых задач упаковки: нужно поместить заданные объекты в некие «чемоданы» максимально «плотно».

В геометрических задачах упаковки понятие «плотности» похоже на привычное: требуется оставить как можно меньше свободной площади или объема предоставленного «чемодана». А иногда свободного места не остается совсем, и тогда главной задачей математика является упаковка всех объектов. На самом деле, даже для таких случаев существуют интересные приемы и способы решения.

Головоломка Слотобера-Граатсмы относится как раз к таким задачам. В качестве «чемодана» у нас будет куб 3×3×3, а упаковать нам нужно девять объектов: шесть блоков из четырех единичных кубиков 1×2×2 и три единичных блока 1×1×1. Несложно убедиться, что блоки должны занимать куб полностью. Выглядит просто? Что ж, давайте попробуем!

Вполне вероятно, что «методом тыка» уложить все блоки не получится. Значит, настало время математических методов! Первое, что можно заметить – если разместить в «чемодане» большие блоки, в оставшиеся пазы войдут три единичных кубика, ведь условий на их положение нет. Поэтому стоит обратить внимание на первую шестерку блоков. И вот тут можно заметить вторую особенность: эти блоки – плоские, состоят из одного ряда кубиков, поэтому и большой куб можно рассматривать как три «слоя» в каждом направлении. Как может быть расположен блок относительно таких «слоев»? На самом деле, возможны только три варианта: блок полностью находится в данном слое, блок с ним не пересекается, и блок «перпендикулярен» – только два из четырех кубиков блока принадлежат данному слою.

Отсюда можно сделать ключевой вывод нашего решения: как бы не располагались большие блоки, в любом слое в любом направлении они заполнят четное число кубиков! Но так как слои состоят из 9 ячеек, то в каждом из должно остаться хотя бы одно «свободное место» для единичного блока. Получается, что расположить кубики 1×1×1 нужно строго по одному в каждом слое для каждого направления: например, вдоль большой диагонали куба. Попробуйте расположить единичные блоки таким образом: куб оказывается разбит на две симметричные части, в которые оставшиеся элементы помещаются с первой попытки. «Чемодан» полностью укомплектован – задача упаковки в трехмерном пространстве решена!