Вспомнилось давнее.
Придумать пример (трехмерного) многогранника, удовлетворяющего условиям:
1) К каждой вершине примыкают ровно три ребра (= многогранник простой)
2) Все грани имеют чётное число сторон
3) Его грани нельзя покрасить в три цвета правильным образом (т.е. так чтобы смежные грани были разных цветов).
Грани должны быть обычными многоугольниками, без дырок. Отдельно: доказать, что таких выпуклых многогранников не бывает.
Интересующимся: изучить "монодромию" красок при путешествиях по рёбрам.
Решение.
ОтветитьУдалитьВолшебное слово здесь -- монодромия. Ответ таков: многогранников с указанным свойством и сферической границей не существует, доказательство ниже. Поэтому в качестве решения надо искать многогранник с дырками. Например, такой, граница которого -- тор. Теперь доказательство:
Сопоставим каждой вершине v трехэлементное множество F_v примыкающих к ней граней. Если две вершины соединены ребром, то определено каноническое отображение f_e:F_v-->F_w (общие грани переходят сами в себя, а оставшаяся --- в оставшуюся). Если есть цепочка из ребер (путь), то можно определить композицию отображений очевидным образом. Если есть цикл с началом и концом в v, то, соответственно, получается некоторая перестановка множества F_v (такую перестановку логично назвать монодромией петли). Утверждение: многогранник можно правильно покрасить в 3 цвета <=> когда монодромии по всем петлям являются тождественными перестановками. Действительно, просто красим все грани последовательно так, чтобы было выполнено условие правильности раскраски. Такой способ корректен из-за тривиальности монодромии.
Условие четности грани влечет за собой, что монодромия вдоль границы любой грани является тождественной перестановкой. Отсюда и из нехитрых топологических выкладок можно вывести, что монодромия определена не просто на петлях, но и на классах гомотопии петель. Поэтому если многогранник выпуклый (или, более общо, односвязный) то монодромия всегда тривиальна, значит многогранник раскрашивается. А чтобы нарисовать нераскрашиваемый многогранник, надо взять что-то с неодносвязной границей, например, тор и сделать так, чтобы монодромия вдоль, скажем, меридиана тора была нетривиальной.
Такой тор можно задать как склейку квадрата, но выпуклой реализации он не имеет. Действительно, если у многогранника в каждой вершине сходится 3 ребра, то этот многогранник --- выпуклый, а значит тором быть не может.
Ответ к задаче: таких геометрических многогранников не бывает. Пример комбинаторного многогранника, дающего решение, -- на картинке.
Есть более общее утверждение: если n-мерный многогранник простой (в любой вершине сходятся n граней) и все его 2-мерные грани -- четноугольники, то его гиперграни можно раскрасить в n цветов правильным образом. Доказательство абсолютно аналогично --- через монодромию и стягиваемость любой петли. См. http://arxiv.org/abs/math/0102186