На Всеросе была предложена такая задача (автор Ю. А. Хромин):

куб составлен из n³ единичных кубиков. В них надо написать числа 0,1 так, чтобы сумма восьми чисел в любом кубе со стороной 2 была не больше 4, и при таких ограничениях общая сумма была максимально возможной.

Задача решается, например, по индукции (так почти все участники, решившие задачу, и делали).

Но Артур Абзалилов из Казани предложил гораздо более интересный подход, который позволяет решить любую задачу такого рода, навроде:

в кубиках параллелепипеда 1000×2000×3000 расставляются числа 0,1, 2, 3. Расстановка допустимая, если сумма 343 чисел в любом кубе со стороной 7 не больше 800. Найдите наибольшую сумму чисел в допустимой расстановке.

Далее подход Артура объясняется на этом примере.


Давайте сделаем произвольную допустимую расстановку X 7-периодичной в данном направлении (по вертикали, скажем) — сохраняя допустимость и не уменьшая сумму чисел. Разобьём всё на двумерные горизонтальные слои и выберем 7 подряд идущих слоёв с наибольшей суммой. Пусть общая сумма в выбранных слоях это s. Рассмотрим расстановку Y, которая в выбранных 7 слоях совпадает с X, но 7-периодична по вертикали. Ясно, что она тоже допустима. Докажем, что сумма чисел в Y не меньше, чем в X. Достаточно доказать это отдельно для слоёв ниже выбранных и выше выбранных. Слои ниже выбранных разобьём на семёрки, начиная с нижнего, верхняя семёрка будет, возможно, пересекаться с выбранными слоями. В каждой семёрке сумма в X не больше, чем s, а в Y — ровно s. Значит, сумма в Y ниже выбранных слоёв не больше, чем в X (сумма в части выбранных слоёв сократилась: они одинаковы в X и в Y). То же сверху от выбранных.

Теперь делаем то же последовательно в двух других направлениях и получаем допустимую расстановку с суммой не меньше чем в исходной, но 7-периодическую по каждой переменной.

Среди таких расстановок найти ту, где сумма наибольшая, несложно: надо раскрасить кубики в 343 цвета в зависимости от остатков координат при делении на 7, в 266 самых популярных цветах расставить тройки, в следующем по популярности цвете расставить 2, в остальных кубиках нули. Получается 14013662520, если я не обсчитался.