avva | решение задачки

Решение вчерашней задачи про муравьев на многограннике.

На поверхности многогранника можно "нарисовать" граф следующим образом. В центре каждой грани ставим вершину графа. Если у двух граней есть общая сторона, соединяем их центры ребром графа; можно представить себе для наглядности, как это ребро идет из центра одной грани в середину общей стороны, и оттуда по второй грани в ее центр. Например, если наш многогранник - тетраэдр, то из каждой вершины графа (центра грани) будет выходить три ребра; если куб, то четыре.

(чтобы дальше не путаться, я буду ребра исходного многогранника называть "сторонами", а ребра только что описанного графа - "ребрами").

Без ограничения общности можно предположить, что все муравьи находятся в начальный момент не в вершинах многогранника, а внутри сторон своих граней, так что у каждого муравья есть определенная сторона, на которой он в начальный момент находится. Если ребро графа пересекает сторону, на которой есть муравей, покрасим это ребро в красный цвет.

Далее, мы можем предположить, что вначале ни на одной стороне нет более одного муравья. Почему? Если они есть и идут навстречу, то задача уже решена; если они есть и расходятся друг от друга, то подождем какое-то время, пока во всех таких случаях они не сойдут с общей стороны. На другую сторону за это время два муравья одновременно не зайдут (если зайдут, опять-таки задача решена).

Теперь докажем, что в графе, соответствующем многограннику с описанными выше условиями (на каждой стороне не больше одного муравья, и все муравьи внутри сторон, а не в вершинах) есть красный цикл. Начиная с любой вершины, т.е. с центра любой грани, будем двигаться от вершины к вершине по красным ребрам следующим образом. Поскольку "наш" муравей, муравей нашей текущей грани, находится внутри какой-то стороны, ребро, пересекающее ее - красное, и мы выйдем именно через него. У следующей грани будет "свой" муравей, и мы выйдем по красному ребру, пересекающему его сторону, и так далее. Таким образом, мы никогда не выйдем по тому ребру, через которое зашли, потому что это соответствует двум муравьям на одной стороне многогранника. Т.к. кол-во граней конечно, рано или поздно мы замкнем цикл.

Наконец, запустим время вперед, муравьи начинают двигаться. Пока все муравьи, связанные с ребрами нашего красного цикла, не пересекают вершин многогранника, а только двигаются по своим сторонам, все красные ребра остаются красными и цикл не изменяется. Теперь представьте, что какой-то муравей пересекает вершину многогранника. Ребро графа, пересекаюшее сторону, с которой он ушел, перестало теперь быть красным, и цикл разомкнулся. Но образовалось новое красное ребро, пересекающее сторону многогранника, на которую он перешел - и оно ведет "внутрь" поверхности многогранника, которую отделял исходный цикл. Если мы остановим на секунду муравьев, и продолжим, как раньше, идти по красным ребрам начиная с нового, мы опять замкнем красный цикл, и все его ребра будут лежать внутри площади, которую отделял прошлый цикл. Поэтому со временем площадь, которую отделяет на поверхности многогранника красный цикл, уменьшается, пока не дойдет до нуля - цикл превратится в петлю из двух идентичных ребер, т.е. два муравья будут на одном ребре многогранника, и встретятся.

Зрительная аналогия: первоначальный красный цикл похож на ломаное лассо, которое набросили на многогранник, и по мере того, как муравьи переходят со стороны на сторону, это лассо сжимается, пока не доходит до нуля.

Статья, в которой был доказан этот результат, и использован в теории групп:

Klyachko Ant. A funny property of a sphere and equations over groups. Comm. Algebra 1993 V.21 P.2555-2575

За наводку на эту статью и соответственно решение задачи выражаю благодарность