задачка (математическое)

[avva]

Возможно, эта задачка непростая. Я ее пока не решил. Условие красивое.

Дан выпуклый многогранник. На каждой грани сидит муравей, и ползет по периметру своей грани против часовой стрелки. Все муравьи ползут с одинаковой скоростью. Доказать, что рано или поздно два муравья встретятся.

Comments

[eisenberg.livejournal.com]

Короче, всё это топология. Скорости и размеры ни при чём; пусть ползут как угодно, лишь бы назад не пятились. Многогранник - это тот же плоский граф. Разложим его на плоскости. Объединим две грани, оставив на них одного муравья (если для того графа существовал способ обхода, то и для этого будет; но тут могут понадобиться какие-то ещё сильные волшебные слова). И так пообъединяем все грани, пока не получится двугранник - одна грань, по которой ползут двое в разные стороны.
На торе бы им это удалось.

[(Anonymous)]

ха, я первый успел!

[eisenberg.livejournal.com]

Вот чёрт.

[avva.livejournal.com]

Волшебные слова помогли бы, я не уверен, что понимаю, суть такого объединения обходов. Если до объединения оба муравья могли одновременно находится вне общего ребра (почему бы и нет), то один муравей их общее движение никак не отсимулирует, кажется?

[eisenberg.livejournal.com]

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

[timur0.livejournal.com]

ждем "сильные волшебные слова", потому как далеко не очевидно, что при объединении граней будет способ обхода.