Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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


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

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

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

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

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

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

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

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

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

За наводку на эту статью и соответственно решение задачи выражаю благодарность falcao.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments