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

[avva]

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


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

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

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

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

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

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

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

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

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

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

Comments

[panikowsky.livejournal.com]

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

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

Или я что-то путаю?

[avva.livejournal.com]

На ребрах, принадлежащих грани N, есть точно один муравей-хозяин, и возможно несколько муравьев-гостей - все эти муравьи на разных ребрах. Но заходим мы в N всегда *не* через ребро, на котором хозяин N - потому что мы заходим через ребро, на котором хозяин предыдущей грани M, а на этом ребре нет одновременно двух муравьев. Поэтому мы всегда заходим через "гостя", а значит можем выйти через "хозяина".

[panikowsky.livejournal.com]

А! То есть идея в том, чтобы выходить всегда через "хозяина". Там сказано "можно", а должно быть "нужно". :)

Спасибо!

[avva.livejournal.com]

Да, спасибо, отредактировал чуток, чтобы было понятнее.

[(Anonymous)]

Не совсем понятно, что такое «внутри», и почему внутри. То есть понятно, но не сразу. Можно бы и поподробнее.

[(Anonymous)]

Извините, пожалуйста, какое-то склочное замечание получилось. На самом деле — хорошо рассказанное красивое доказательство.

[avva.livejournal.com]

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

Эту небольшую техническую неприятность можно решить разными способами. Например, мы можем притвориться, будто муравьи вообще не проползают через вершины: давайте поставим очень-очень близко к каждой вершине на пути каждого муравья пару гипотетических нуль-транспортировщиков, так, что муравей "перепрыгивает" через вершину, потом ждет немножко - то время, за которое он бы обычно там прополз - и ползет дальше. Если мы выберем "очень-очень близко" так, что у другого муравья не будет шанса как раз случайно оказаться рядом на соседней стороне, так что мы через него "нуль-перепрыгнем", то в расписании возможных встреч ничего не изменится, и все остальное доказательство будет работать. А выбрать такое малое "очень-очень близко" можно, предполагая, что муравьи движутся каждый по определенному маршруту, просто взяв минимум всех расстояний между всеми парами муравьев за весь период общего движения. Кажется, примерно это я имел в виду, когда сказал без ограничения общности, можно считать, что муравьев в вершинах нет.

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

[(Anonymous)]

Я как раз не это имел в виду. «Внутри» — имеется в виду внутри поверхности многогранника, ограниченной (бывшим) красным циклом. Понятно, что цикл нужно ориентировать против часовой, тогда «внутри» определяется однозначно. Можно также рассказать поподробнее, почему новый цикл будет внутри старого.

[avva.livejournal.com]

Главное ориентировать всех муравьев одинаково; можно и по часовой. Любой цикл делит поверхность многогранника на две части. Используя заданную на многограннике ориентацию движения - напр. против часовой стрелки - мы можем однозначно определить, какая из двух частей нас интересует в том смысле, что она будет сжиматься со временем. А именно: каждое ребро цикла пересекает сторону многогранника, по которой ползет муравей. Скажем, что он ползет "снаружи вовнутрь", пересекая границу цикла в момент пересечения середины своей стороны. Тогда для всех муравьев, участвующих в цикле, "внутри" окажется с одной и той же стороны цикла, а "снаружи" с другой (как раз для этого нужно исходное требование, чтобы они все ползли против часовой, а не каждый как хочет). Та часть, которая "внутри", будет сжиматься; почему? потому что муравей, доползая до вершины многогранника, находится уже "внутри" по определению, и та сторона, на которую он переползает и которая породит новое красное ребро, тоже находится "внутри". Цикл, который начинается с нового ребра, может перестать быть "внутри", только пересекая какую-то вершину старого цикла, но дойдя до нее, он тем самым тут же замкнет новый цикл. Поэтому у него нет возможности оказаться "снаружи".

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

[vasgen-gorapost.livejournal.com]

красиво, да

[aldanur.livejournal.com]

“Ant.” – отлично :)

[jewgeniusz.livejournal.com]

:-) Да, неплохо получилось.

От Капитана Очевидность: есть двое алгебраистов, которых зовут A.A.Klyachko. Александр, который работает в Турции, и Антон, который работает в Москве на мехмате.

[(Anonymous)]

Где использована выпуклость исходного многогранника? Похоже, ее и не надо?
То же -- про одинаковую скорость муравьев. Ну, понятно, что если, скажем, один едва ползет, то его всегда успеют встретить. А с другой стороны, замри они все -- все испортится. Любые ненулевые скорости, что ли -- так и постоянства не надо, достаточно чего-то типа "не слишком бессовестно тормозя" в смысле "путь со временем не ограничен"...

[(Anonymous)]

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

[protopopov-m.livejournal.com]

По многограннику топологически эквивалентному тору можно ползать до бесконечности.

[protopopov-m.livejournal.com]

На самом деле, цикл действительно переходит "внутрь", но дело в том, что он может сменить ориентацию и начать двигаться в другую сторону.

Пример смены ориентации и окончательное решение задачи можно найти здесь http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1063636174/20 (http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1063636174/20)

оффтоп

[falcao.livejournal.com]

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

http://falcao.livejournal.com/180432.html