ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65858
Темы:    [ Правильные многогранники (прочее) ]
[ Четность и нечетность ]
[ Инварианты ]
[ Четность перестановки ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Муравей ползает по замкнутому маршруту по рёбрам додекаэдра, нигде не разворачиваясь назад. Маршрут проходит ровно два раза по каждому ребру.
Докажите, что некоторое ребро муравей оба раза проходит в одном и том же направлении.


Решение 1

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

  В любом случае, чётность количества циклов сохраняется. Если все перекрёстки левые, то будет 12 циклов (соответствующих граням додекаэдра). Значит, один цикл никогда не получится.

Решение 2

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

Замечания

8 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 27
Дата 2005/2006
вариант
Вариант весенний тур, основной вариант, 10-11 класс
задача
Номер 7

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .