Оценка + пример

Положим Введём систему координат так, что все вершины единичных кубиков будут иметь целые координаты от 0 до

Начнём с примера, показывающего, что количество чёрных кубиков действительно может быть равно У каждого кубика рассмотрим его вершину, ближайшую к началу координат (её координаты принимают значения от 0 до ). Пусть кубик чёрный, если хотя бы две координаты этой вершины чётны, и белый иначе. Ясно, что тогда в любом кубе будет ровно 4 чёрных и 4 белых кубика. При этом количество чёрных кубиков, у которых все три соответствующих координаты чётны, равно а количество кубиков, у которых чётны ровно две координаты, равно поэтому общее количество чёрных кубиков будет равно

Осталось доказать, что этот пример оптимальный. Пусть куб сложен из чёрных и белых кубиков так, что выполнены условия задачи. Назовём кубик тёмным или светлым, если он является соответственно чёрным или белым в приведённом выше примере.

Для каждой точки с координатами в большом кубе назовём её - и -рангом соответственно числа

Назовём рангом этой точки число Иначе говоря, - или -ранг точки — это расстояние от неё до ближайшей грани большого куба, перпендикулярной соответствующей оси, а её ранг — это просто расстояние от неё до ближайшей грани большого куба.

Отметим все вершины единичных кубиков с нечётными рангами. Для каждой отмеченной вершины рассмотрим разность количеств чёрных и белых кубиков, сходящихся в этой вершине; поскольку все эти вершины являются центрами кубов эта разность неположительна. Значит, и сумма всех таких разностей неположительна.

Скажем, что кратность единичного кубика — это количество его отмеченных вершин (столько раз этот кубик учтён в ). Тогда равна разности суммы всех кратностей чёрных кубиков и суммы кратностей всех белых кубиков. Поэтому нам достаточно доказать, что если такая разность неположительна, то количество чёрных кубиков не превосходит

Пусть и — это -, - и -ранги центра некоторого кубика; пусть для определённости Тогда нетрудно видеть, что

• если то кратность этого кубика равна 4;

• если

  

  где чётно, то кратность кубика меньше 4, и он тёмный;

• если

  

  где нечётно, то кратность кубика больше 4, и он светлый.

Итак, кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4.

Пусть теперь

— кратности всех кубиков, расположенные в неубывающем порядке. Из сказанного выше вытекает, что

поскольку в приведённом выше примере значение было равно 0.

Если теперь в рассматриваемой раскраске чёрных кубиков, то

поскольку Это противоречие показывает, что что и требовалось доказать.