|
|
 |
Условие
Муравей ползает по замкнутому маршруту по рёбрам додекаэдра, нигде не разворачиваясь назад. Маршрут проходит ровно два раза по каждому ребру.
Докажите, что некоторое ребро муравей оба раза проходит в одном и том же направлении.
Решение 1
Предположим, что это не так. Тогда на каждом перекрёстке все три раза муравей поворачивает либо только налево, либо только направо. Расположим произвольно левые и правые перекрестки в вершинах додекаэдра и рассмотрим соответствующие маршруты муравья. Получим набор циклов. При замене "знака" одного из перекрёстков происходит перестройка: если к перекрёстку подходит три цикла, они склеиваются в один, если два – они переклеиваются в два другие, если один – остаётся один или он распадается на три (см. рисунки).
Решение 2
Докажем равносильное утверждение: если все рёбра пройдены муравьём в обоих направлениях, то в какой-то вершине муравей повернул назад.
Зададим две перестановки на множестве направленных рёбер додекаэдра: p переводит каждое ребро в следующее на маршруте, а t меняет на каждом ребре направление на противоположное. Заметим, что если ребро e входит в некоторую вершину v, то p(e) выходит из неё, а t(p(e)) снова входит в v. Обозначим через sv перестановку, выполняемую tp на множестве рёбер, входящих в v. Тогда tp распадается в произведение 20 перестановок sv – по одной для каждой вершины додекаэдра. Перестановка p – цикл длины 60 – нечётна, а t – произведение 30 транспозиций – чётна. Поэтому перестановка tp нечётна, а значит, хотя бы одна из перестановок sv нечётна. Нечётная перестановка трёх рёбер может либо оставлять все рёбра на месте, либо переставлять два ребра, а третье оставлять на месте. Вот на этом-то третьем ребре муравей и повернул вспять!
Замечания
8 баллов
