Question

. Куб 100100100 составлен из кубиков 111, некоторые из которых покрашены в чёрный цвет, а остальные в белый так, что в каждом параллелепипеде 11100, состоящем из 100 единичных кубиков, ровно два чёрных кубика и между ними расположено чётное число белых (возможно, 0). Докажите, что можно перекрасить половину чёрных кубиков в белый цвет так, чтобы в каждом параллелепипеде 11100 остался ровно один чёрный кубик.

Answer 1

Выберем вершину большого куба и покрасим три ребра, исходящие из неё, в красный, зелёный и синий цвета. Теперь на каждом маленьком кубике напишем, сколько кубиков нужно пройти, двигаясь параллельно красному отрезку, сколько - параллельно синему отрезку и сколько - параллельно зелёному, чтобы в итоге оказаться в кубике, примыкающем к выбранной вершине (предполагается, что записано минимальные "расстояния"). Рассмотрим два чёрных кубика в одной "полоске". Чётности сумм их "расстояний" различны. Действительно, так как между ними чётное количество кубиков, то чтобы добраться от одного чёрного кубика до другого, придётся "пройти" нечётное число кубиков (считая тот, в который пришли). Теперь давайте выкрасим в белый цвет все кубики, сумма "расстояний" для которых нечётна. В каждой "полоске" был убран ровно один чёрный кубик, следовательно, ровно один чёрный кубик остался.

Answer 2

Давайте сформулируем данную задачу в терминах графов. Представим куб 100x100x100 как граф, где каждый узел представляет собой кубик 1x1x1, а ребра соединяют соседние кубики.

Теперь давайте пронумеруем кубики, покрашенные в черный цвет, числами от 1 до N (где N - количество черных кубиков). Предположим, что в каждом параллелепипеде 1x1x100 есть A черных кубиков и B белых кубиков (A + B = 100).

Создадим два вида графов: исходный граф и граф после перекраски половины черных кубиков в белый цвет.

В исходном графе у нас есть N вершин и ребра между некоторыми из них, образующими параллелепипеды 1x1x100. Мы знаем, что в каждом таком параллелепипеде у нас ровно 2 черных кубика. Следовательно, каждая вершина в исходном графе имеет степень 2.

В графе после перекраски у нас также есть N вершин и ребра между некоторыми из них, образующими параллелепипеды 1x1x100. Мы хотим перекрасить половину черных кубиков, то есть N/2 кубиков, в белый цвет. Это означает, что у каждой вершины в перекрашенном графе степень будет равна 1, так как после перекраски в каждом параллелепипеде останется ровно один черный кубик.

Теперь, чтобы завершить доказательство, давайте рассмотрим две возможности:

1. Если A четно:

   • Так как в каждом параллелепипеде 1x1x100 у нас ровно A черных кубиков, то перекраска половины из них (N/2 = A/2) в белый цвет возможна.
   • В исходном графе у каждой вершины степень 2, и перекраска половины из них в белый цвет приведет к графу, в котором у каждой вершины степень 1.

2. Если A нечетно:

   • Так как в каждом параллелепипеде 1x1x100 у нас ровно A черных кубиков, то перекраска (N + 1)/2 черных кубиков в белый цвет приведет к тому, что останется (N - 1)/2 черных кубиков.
   • В исходном графе у каждой вершины степень 2, и перекраска (N + 1)/2 из них в белый цвет также приведет к графу, в котором у каждой вершины степень 1.

Таким образом, в обоих случаях можно перекрасить половину черных кубиков в белый цвет так, чтобы в каждом параллелепипеде 1x1x100 остался ровно один черный кубик. Задача доказана.