ВсОШ 2025, 11 класс, задача 4
Дано натуральное число . Куб со стороной сложен из единичных кубиков, каждый из которых — либо чёрный, либо белый. Оказалось, что среди любых кубиков, имеющих общую вершину и образующих куб , не более чёрных кубиков. Какое наибольшее количество чёрных кубиков могло быть использовано?
Ответ. .
Решение. Положим . Введём систему координат так, что все вершины единичных кубиков будут иметь целые координаты от до .
Начнём с примера, показывающего, что количество чёрных кубиков действительно может быть равно . У каждого кубика рассмотрим его вершину, ближайшую к началу координат (её координаты принимают значения от до ). Пусть кубик чёрный, если хотя бы две координаты этой вершины чётны, и белый иначе. Ясно, что тогда в любом кубе будет ровно чёрных и белых кубика. При этом количество чёрных кубиков, у которых все три соответствующих координаты чётны, равно , а количество кубиков, у которых чётны ровно две координаты, равно , поэтому общее количество чёрных кубиков будет равно .
Осталось доказать, что этот пример оптимальный. Пусть куб сложен из чёрных и белых кубиков так, что выполнены условия задачи. Назовём кубик тёмным или светлым, если он является соответственно чёрным или белым в приведённом выше примере.
Для каждой точки с координатами в большом кубе назовём её -, - и -рангом числа
соответственно. Назовём рангом этой точки число . Иначе говоря, -, - или -ранг точки — это расстояние от неё до ближайшей грани большого куба, перпендикулярной соответствующей оси, а её ранг — это просто расстояние от неё до ближайшей грани большого куба.
Отметим все вершины единичных кубиков с нечётными рангами. Для каждой отмеченной вершины рассмотрим разность количеств чёрных и белых кубиков, сходящихся в этой вершине; поскольку все эти вершины являются центрами кубов , эта разность неположительна. Значит, и сумма всех таких разностей неположительна.
Скажем, что кратность единичного кубика — это количество его отмеченных вершин (столько раз этот кубик учтён в ). Тогда равна разности суммы всех кратностей чёрных кубиков и суммы кратностей всех белых кубиков. Поэтому нам достаточно доказать, что если такая разность неположительна, то количество чёрных кубиков не превосходит .
Пусть , и — это -, - и -ранги центра некоторого кубика; пусть для определённости . Тогда нетрудно видеть, что:
- если , то кратность этого кубика равна ;
- если , где чётно, то кратность кубика меньше , и он тёмный;
- если , где нечётно, то кратность кубика больше , и он светлый.
Итак, кратности всех тёмных кубиков не больше , а всех светлых — не меньше .
Пусть теперь
— кратности всех кубиков, расположенные в неубывающем порядке. Из сказанного выше вытекает, что
поскольку в приведённом выше примере значение было равно .
Если теперь в рассматриваемой раскраске чёрных кубиков, то
поскольку . Это противоречие показывает, что , что и требовалось доказать.
Замечание. Оценку можно доказать и по-другому — например, так.
Рассмотрим четыре вершины большого куба , , , , образующие правильный тетраэдр. Отметим вершину единичного кубика, если у вектора, соединяющего её с ближайшей к ней вершиной из , , и , все координаты нечётны. Пусть — количество отмеченных вершин, а — количество единичных кубиков, не имеющих отмеченной вершины. Тогда количество чёрных кубиков не превосходит .
Осталось выяснить, что . Это можно сделать непосредственно; но вместо этого можно воспользоваться той же схемой, что и в решении выше. Именно, нетрудно заметить, что если у единичного кубика есть две отмеченных вершины, то он светлый, а если нет отмеченных вершин, то он тёмный. Тогда рассуждение выше сработает с несложными изменениями.