Разделы 
Дополнительно
Задача по математике - 1875
2019-01-21 
Куб $n \times n \times n$ сложен из единичных кубиков. Дана замкнутая несамопересекающаяся ломаная, каждое звено которой соединяет центры двух соседних (имеющих общую грань) кубиков. Назовем отмеченными грани кубиков, пересекаемые данной ломаной. Докажите, что ребра кубиков можно покрасить в два цвета так, чтобы каждая отмеченная грань имела нечетное число, а всякая неотмеченная грань - четное число сторон каждого цвета.
Решение:
Пусть $PQ$ - любое горизонтальное ребро одного из кубиков. Обозначим через $C_{PQ}$ вертикально расположенный прямоугольник, нижняя сторона которого - $PQ$, а верхняя лежит на поверхности куба. Пусть $n_{PQ}$ - число пересечений данной ломаной с прямоугольником $C_{PQ}$. Ребро $PQ$ покрасим в белый цвет, если $n_{PQ}$ четно, и в черный, если $n_{PQ}$ нечетно. Все остальные, т. е. вертикальные ребра кубиков, покрасим в белый цвет.
Докажем теперь, что приведенная раскраска удовлетворяет условию задачи.
Пусть $PQRS$ - вертикальная грань и $PQ$ и $RS$ - ее горизонтальные ребра. Если ломаная не пересекает $PQRS$, то прямоугольники $C_{Pq}$ и $C_{RS}$ пересекаются с ломаной в одних и тех же точках. Поэтому ребра $PQ$ и $RS$ покрашены в один цвет, и, следовательно, эта грань удовлетворяет требованию задачи. Если же ломаная пересекает прямоугольник $PQRS$, то $n_{PQ}$ и $n_{RS}$ отличаются на 1 и, следовательно, имеют разную четность. Поэтому ребра $PQ$ и $RS$ покрашены в разные цвета, что означает выполнение условия задачи и в этом случае.
Пусть теперь $PQRS$ - горизонтальная грань. Объединение прямоугольников $C_{PQ}, C_{QR}, C_{RS}$ и $C_{SP}$ есть боковая поверхность параллелепипеда, состоящего из кубиков, расположенных в точности над гранью $PQRS$. Замкнутая ломаная пересекает поверхность параллелепипеда четное число раз (сколько раз ломаная заходит внутрь параллелепипеда, столько раз она и «выходит» из него).
Заметим, что ломаная не пересекает верхнюю грань параллелепипеда. Если грань $PQRS$ не отмечена, то ломаная не пересекает ее. Тогда все точки пересечения ломаной с поверхностью параллелепипеда расположены на его боковой поверхности. В этом случае сумма $n_{PQ}+ n_{QR} + n_{RS} + n_{SP}$ четна. Поэтому число сторон грани $PQRS$, отмеченных черным цветом, четно.
Если же грань $PQRS$ отмечена, то одна из точек пересечения ломаной с поверхностью параллелепипеда принадлежит $PQRS$. Тогда сумма $n_{PQ} + n_{QR} + n_{RS} + n_{SP}$ нечетна и, следовательно, нечетное число сторон грани $PQRS$ окрашено в черный цвет.
Куб $n \times n \times n$ сложен из единичных кубиков. Дана замкнутая несамопересекающаяся ломаная, каждое звено которой соединяет центры двух соседних (имеющих общую грань) кубиков. Назовем отмеченными грани кубиков, пересекаемые данной ломаной. Докажите, что ребра кубиков можно покрасить в два цвета так, чтобы каждая отмеченная грань имела нечетное число, а всякая неотмеченная грань - четное число сторон каждого цвета.
Решение:
Пусть $PQ$ - любое горизонтальное ребро одного из кубиков. Обозначим через $C_{PQ}$ вертикально расположенный прямоугольник, нижняя сторона которого - $PQ$, а верхняя лежит на поверхности куба. Пусть $n_{PQ}$ - число пересечений данной ломаной с прямоугольником $C_{PQ}$. Ребро $PQ$ покрасим в белый цвет, если $n_{PQ}$ четно, и в черный, если $n_{PQ}$ нечетно. Все остальные, т. е. вертикальные ребра кубиков, покрасим в белый цвет.
Докажем теперь, что приведенная раскраска удовлетворяет условию задачи.
Пусть $PQRS$ - вертикальная грань и $PQ$ и $RS$ - ее горизонтальные ребра. Если ломаная не пересекает $PQRS$, то прямоугольники $C_{Pq}$ и $C_{RS}$ пересекаются с ломаной в одних и тех же точках. Поэтому ребра $PQ$ и $RS$ покрашены в один цвет, и, следовательно, эта грань удовлетворяет требованию задачи. Если же ломаная пересекает прямоугольник $PQRS$, то $n_{PQ}$ и $n_{RS}$ отличаются на 1 и, следовательно, имеют разную четность. Поэтому ребра $PQ$ и $RS$ покрашены в разные цвета, что означает выполнение условия задачи и в этом случае.
Пусть теперь $PQRS$ - горизонтальная грань. Объединение прямоугольников $C_{PQ}, C_{QR}, C_{RS}$ и $C_{SP}$ есть боковая поверхность параллелепипеда, состоящего из кубиков, расположенных в точности над гранью $PQRS$. Замкнутая ломаная пересекает поверхность параллелепипеда четное число раз (сколько раз ломаная заходит внутрь параллелепипеда, столько раз она и «выходит» из него).
Заметим, что ломаная не пересекает верхнюю грань параллелепипеда. Если грань $PQRS$ не отмечена, то ломаная не пересекает ее. Тогда все точки пересечения ломаной с поверхностью параллелепипеда расположены на его боковой поверхности. В этом случае сумма $n_{PQ}+ n_{QR} + n_{RS} + n_{SP}$ четна. Поэтому число сторон грани $PQRS$, отмеченных черным цветом, четно.
Если же грань $PQRS$ отмечена, то одна из точек пересечения ломаной с поверхностью параллелепипеда принадлежит $PQRS$. Тогда сумма $n_{PQ} + n_{QR} + n_{RS} + n_{SP}$ нечетна и, следовательно, нечетное число сторон грани $PQRS$ окрашено в черный цвет.
