решение задачки
Sep. 3rd, 2009 08:10 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaРешение вчерашней задачи про муравьев на многограннике.
На поверхности многогранника можно "нарисовать" граф следующим образом. В центре каждой грани ставим вершину графа. Если у двух граней есть общая сторона, соединяем их центры ребром графа; можно представить себе для наглядности, как это ребро идет из центра одной грани в середину общей стороны, и оттуда по второй грани в ее центр. Например, если наш многогранник - тетраэдр, то из каждой вершины графа (центра грани) будет выходить три ребра; если куб, то четыре.
(чтобы дальше не путаться, я буду ребра исходного многогранника называть "сторонами", а ребра только что описанного графа - "ребрами").
Без ограничения общности можно предположить, что все муравьи находятся в начальный момент не в вершинах многогранника, а внутри сторон своих граней, так что у каждого муравья есть определенная сторона, на которой он в начальный момент находится. Если ребро графа пересекает сторону, на которой есть муравей, покрасим это ребро в красный цвет.
Далее, мы можем предположить, что вначале ни на одной стороне нет более одного муравья. Почему? Если они есть и идут навстречу, то задача уже решена; если они есть и расходятся друг от друга, то подождем какое-то время, пока во всех таких случаях они не сойдут с общей стороны. На другую сторону за это время два муравья одновременно не зайдут (если зайдут, опять-таки задача решена).
Теперь докажем, что в графе, соответствующем многограннику с описанными выше условиями (на каждой стороне не больше одного муравья, и все муравьи внутри сторон, а не в вершинах) есть красный цикл. Начиная с любой вершины, т.е. с центра любой грани, будем двигаться от вершины к вершине по красным ребрам следующим образом. Поскольку "наш" муравей, муравей нашей текущей грани, находится внутри какой-то стороны, ребро, пересекающее ее - красное, и мы выйдем именно через него. У следующей грани будет "свой" муравей, и мы выйдем по красному ребру, пересекающему его сторону, и так далее. Таким образом, мы никогда не выйдем по тому ребру, через которое зашли, потому что это соответствует двум муравьям на одной стороне многогранника. Т.к. кол-во граней конечно, рано или поздно мы замкнем цикл.
Наконец, запустим время вперед, муравьи начинают двигаться. Пока все муравьи, связанные с ребрами нашего красного цикла, не пересекают вершин многогранника, а только двигаются по своим сторонам, все красные ребра остаются красными и цикл не изменяется. Теперь представьте, что какой-то муравей пересекает вершину многогранника. Ребро графа, пересекаюшее сторону, с которой он ушел, перестало теперь быть красным, и цикл разомкнулся. Но образовалось новое красное ребро, пересекающее сторону многогранника, на которую он перешел - и оно ведет "внутрь" поверхности многогранника, которую отделял исходный цикл. Если мы остановим на секунду муравьев, и продолжим, как раньше, идти по красным ребрам начиная с нового, мы опять замкнем красный цикл, и все его ребра будут лежать внутри площади, которую отделял прошлый цикл. Поэтому со временем площадь, которую отделяет на поверхности многогранника красный цикл, уменьшается, пока не дойдет до нуля - цикл превратится в петлю из двух идентичных ребер, т.е. два муравья будут на одном ребре многогранника, и встретятся.
Зрительная аналогия: первоначальный красный цикл похож на ломаное лассо, которое набросили на многогранник, и по мере того, как муравьи переходят со стороны на сторону, это лассо сжимается, пока не доходит до нуля.
Статья, в которой был доказан этот результат, и использован в теории групп:
Klyachko Ant. A funny property of a sphere and equations over groups. Comm. Algebra 1993 V.21 P.2555-2575
За наводку на эту статью и соответственно решение задачи выражаю благодарность![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
falcao.
На поверхности многогранника можно "нарисовать" граф следующим образом. В центре каждой грани ставим вершину графа. Если у двух граней есть общая сторона, соединяем их центры ребром графа; можно представить себе для наглядности, как это ребро идет из центра одной грани в середину общей стороны, и оттуда по второй грани в ее центр. Например, если наш многогранник - тетраэдр, то из каждой вершины графа (центра грани) будет выходить три ребра; если куб, то четыре.
(чтобы дальше не путаться, я буду ребра исходного многогранника называть "сторонами", а ребра только что описанного графа - "ребрами").
Без ограничения общности можно предположить, что все муравьи находятся в начальный момент не в вершинах многогранника, а внутри сторон своих граней, так что у каждого муравья есть определенная сторона, на которой он в начальный момент находится. Если ребро графа пересекает сторону, на которой есть муравей, покрасим это ребро в красный цвет.
Далее, мы можем предположить, что вначале ни на одной стороне нет более одного муравья. Почему? Если они есть и идут навстречу, то задача уже решена; если они есть и расходятся друг от друга, то подождем какое-то время, пока во всех таких случаях они не сойдут с общей стороны. На другую сторону за это время два муравья одновременно не зайдут (если зайдут, опять-таки задача решена).
Теперь докажем, что в графе, соответствующем многограннику с описанными выше условиями (на каждой стороне не больше одного муравья, и все муравьи внутри сторон, а не в вершинах) есть красный цикл. Начиная с любой вершины, т.е. с центра любой грани, будем двигаться от вершины к вершине по красным ребрам следующим образом. Поскольку "наш" муравей, муравей нашей текущей грани, находится внутри какой-то стороны, ребро, пересекающее ее - красное, и мы выйдем именно через него. У следующей грани будет "свой" муравей, и мы выйдем по красному ребру, пересекающему его сторону, и так далее. Таким образом, мы никогда не выйдем по тому ребру, через которое зашли, потому что это соответствует двум муравьям на одной стороне многогранника. Т.к. кол-во граней конечно, рано или поздно мы замкнем цикл.
Наконец, запустим время вперед, муравьи начинают двигаться. Пока все муравьи, связанные с ребрами нашего красного цикла, не пересекают вершин многогранника, а только двигаются по своим сторонам, все красные ребра остаются красными и цикл не изменяется. Теперь представьте, что какой-то муравей пересекает вершину многогранника. Ребро графа, пересекаюшее сторону, с которой он ушел, перестало теперь быть красным, и цикл разомкнулся. Но образовалось новое красное ребро, пересекающее сторону многогранника, на которую он перешел - и оно ведет "внутрь" поверхности многогранника, которую отделял исходный цикл. Если мы остановим на секунду муравьев, и продолжим, как раньше, идти по красным ребрам начиная с нового, мы опять замкнем красный цикл, и все его ребра будут лежать внутри площади, которую отделял прошлый цикл. Поэтому со временем площадь, которую отделяет на поверхности многогранника красный цикл, уменьшается, пока не дойдет до нуля - цикл превратится в петлю из двух идентичных ребер, т.е. два муравья будут на одном ребре многогранника, и встретятся.
Зрительная аналогия: первоначальный красный цикл похож на ломаное лассо, которое набросили на многогранник, и по мере того, как муравьи переходят со стороны на сторону, это лассо сжимается, пока не доходит до нуля.
Статья, в которой был доказан этот результат, и использован в теории групп:
Klyachko Ant. A funny property of a sphere and equations over groups. Comm. Algebra 1993 V.21 P.2555-2575
За наводку на эту статью и соответственно решение задачи выражаю благодарность
falcao.
no subject
Date: 2009-09-06 05:46 am (UTC)То же -- про одинаковую скорость муравьев. Ну, понятно, что если, скажем, один едва ползет, то его всегда успеют встретить. А с другой стороны, замри они все -- все испортится. Любые ненулевые скорости, что ли -- так и постоянства не надо, достаточно чего-то типа "не слишком бессовестно тормозя" в смысле "путь со временем не ограничен"...
no subject
Date: 2009-09-07 05:04 am (UTC)no subject
Date: 2009-09-09 11:35 am (UTC)