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