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

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

Условие

Автор: Фомин С.В.

  а) Четыре порта 1, 2, 3, 4 расположены (в этом порядке) на окружности круглого острова. Их связывает плоская сеть дорог, на которых могут быть перекрёстки, то есть точки, где пересекаются, сходятся или разветвляются дороги. На всех участках дорог введено одностороннее движение так, что, выехав от любого порта или перекрёстка, нельзя вернуться в него снова. Пусть  fij  означает число различных путей, идущих из порта i в порт j. Докажите неравенство   f14f23f13f24.
  б) Докажите, что если портов шесть: 1, 2, 3, 4, 5, 6 (по кругу в этом порядке), то   f16f25f34 + f15f24f36 + f14f26f35f16f24f35 + f15f26f34 + f14f25f36.


Решение

  Введём на каждом пути порядок прохождения портов и развилок.

  а) Рассмотрим всевозможные пары путей, идущих из порта 1 в порт 3 и из 2 – в 4 (рис. 1); коротко будем писать: пары  1 → 3,  2 → 4.  Их число равно  f13f24.  На каждой такой паре есть хоть одна общая точка (развилка или порт). Выберем среди них точку M пути  1 → 3,  ближайшую к порту 1, и поменяем "хвосты" путей, начиная от этой точки M. Так мы получим некоторую пару путей  1 → 4,  2 → 3.  Ясно, что разным парам путей  1 → 3,  2 → 4  при этом соответствуют разные пары  1 → 4,  2 → 3,  поскольку точка M и операция замены "хвостов" определены однозначно. (Более того, ясно, что любая пара
1 → 4,  2 → 3,  имеющая хоть одну общую точку, будет соответствовать некоторой паре  1 → 3,  2 → 4.)
  Отсюда следует неравенство  f14f23f13f24,  поскольку левая часть – это общее число пар путей  1 → 4,  2 → 3  (более точное утверждение: разность
f14f23f13f24  равна числу пар путей  1 → 4,  2 → 3,  не имеющих общих точек).

  б) Среди шести отображений множества  {1, 2, 3}  на  {4, 5, 6}  назовём чётными те, для которых отображение "сохраняет ориентацию треугольника"
(1 → 4, 2 → 5, 3 → 6;  1 → 5, 2 → 6, 3 → 4  и  1 → 6, 2 → 4, 3 → 5,  и нечётными – остальные. Если поменять местами образы каких-то двух из номеров 1, 2, 3, то чётность меняется на противоположную.
  Рассмотрим тройку путей  1 → i,  2 → j,  3 → k,  где  (i, j, k) – некоторая перестановка  (4, 5, 6).  Если какие-то два из них имеют хоть одну общую точку, то выберем самую раннюю из них M (ближайшую к порту 1 на пути  1 → i  или, если  1 → i  не пересекается с двумя другими путями, ближайшую к порту 2 на пути  2 → j)  и поменяем "хвосты" двух путей, проходящих через эту точку. (Если через M проходят все три пути  1 → i,  2 → j,  3 → k,  то меняем хвосты  1 → i  и  2 → j.)  Заметим, что чётность тройки при перемене хвостов меняется. Таким образом, имеется взаимно однозначное соответствие между чётными и нечётными тройками путей, имеющих точки пересечения. Каждая тройка не имеющих общих точек путей имеет вид  1 → 6,  2 → 5,  3 → 4  (рис. 2), то есть нечётна. Значит, нечётных троек не меньше. Отсюда следует требуемое неравенство.

Замечания

баллы: 4 + 6

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

журнал
Название "Квант"
год
Год 1997
выпуск
Номер 2
Задача
Номер М1590
олимпиада
Название Турнир городов
Турнир
Номер 18
Дата 1996/1997
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 5

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

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