|
|
 |
Условие
Куб n×n×n сложен из единичных кубиков. Дана замкнутая несамопересекающаяся ломаная, каждое звено которой соединяет центры двух соседних (имеющих общую грань) кубиков. Назовём отмёченными грани кубиков, пересекаемые данной ломаной. Докажите, что рёбра кубиков можно окрасить в два цвета так, чтобы каждая отмеченная грань имела нечётное число, а всякая неотмеченная грань – чётное число сторон каждого цвета.
Решение
Пусть PQ – горизонтальное ребро одного из кубиков. Обозначим через CPQ вертикально расположенный прямоугольник,
нижняя сторона которого – PQ, а верхняя лежит на поверхности куба.
Пусть nPQ – число пересечений данной ломаной с прямоугольником CPQ. Ребро PQ окрасим в белый цвет, если nPQ чётно, и в чёрный, если nPQ нечётно. Все вертикальные рёбра кубиков, окрасим в белый цвет. Докажем, что приведённая раскраска удовлетворяет условию.
Пусть PQRS – вертикальная грань и PQ и RS – её горизонтальные рёбра. Если ломаная не пересекает PQRS, то
прямоугольники CPQ и CRS пересекаются с ломаной в одних и тех же точках. Поэтому рёбра PQ и RS окрашены в один цвет, и, следовательно, эта грань удовлетворяет условию. Если же ломаная пересекает прямоугольник PQRS, то nPQ и nRS отличаются на 1 и, следовательно, имеют разную чётность. Поэтому ребра PQ и RS окрашены в разные цвета, что означает выполнение условия и в этом случае.
Пусть теперь PQRS – горизонтальная грань. Объединение
прямоугольников CPQ, CQR, CRS и CSP есть боковая поверхность параллелепипеда, состоящего из кубиков, расположенных в точности над гранью PQRS. Замкнутая ломаная пересекает поверхность этого параллелепипеда чётное число раз (сколько раз ломаная заходит внутрь параллелепипеда, столько раз она и выходит из него).
Заметим, что ломаная не пересекает верхнюю грань параллелепипеда.
Если грань PQRS не отмечена, то ломаная не пересекает её. Тогда все точки пересечения ломаной с поверхностью параллелепипеда расположены на его боковой поверхности. В этом случае сумма nPQ + nQR + nRS + nSP чётна. Поэтому число чёрных сторон грани PQRS чётно.
Если же грань PQRS отмечена, то одна из точек пересечения
ломаной с поверхностью параллелепипеда принадлежит PQRS. Тогда сумма
nPQ + nQR + nRS + nSP нечётна и, следовательно, нечётное число сторон грани PQRS окрашено в чёрный цвет.
