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

Проект МЦНМО
при участии
школы 57
Задача 107854
Темы:    [ Связность и разложение на связные компоненты ]
[ Объединение, пересечение и разность множеств ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

  Соответствующий граф связен, иначе пустое множество образует важный набор, но тогда пустое множество – это единственный стратегический набор, а в условии говорится про два различных стратегических набора.
  Рассмотрим некоторый стратегический набор.

  Лемма. При закрытии всех дорог этого набора граф баз распадается ровно на две компоненты связности, причём ни одна из дорог внутри каждой из этих частей не будет закрыта.
  Доказательство. После закрытия стратегического набора множество всех баз разобьётся на компоненты связности. Так как набор важный, этих компонент не менее двух.
  Пусть их хотя бы три. Рассмотрим любую (закрытую) дорогу a, ведущую из одной компоненты связности X в другую компоненту Y (такая дорога найдётся, так как до закрытия граф был связен). Пусть Z – третья компонента связности. Удалим дорогу a из нашего стратегического набора (то есть не будем её закрывать), тогда получится снова важный набор, так как из компоненты X в компоненту Z нельзя проехать, даже пользуясь дорогой a. Но тогда наш набор – не стратегический. Противоречие.
  Рассмотрим любую дорогу внутри одной из компонент связности. Если она закрыта, то, как и выше, выкинем её из стратегического набора. Останется важный набор – противоречие.

  Пусть первый стратегический набор разбивает множество баз на подмножества A и B, а второй – на C и D. Обозначим  K = AC,  L = AD,
M = B
C,  N = BD  (см. рис.).

  Множества K, L, M, N попарно не пересекаются, а их объединение – это множество всех баз. Докажем, что пустым может быть только одно из них (или ни одного). Действительно, если  K = L = ∅,  то A пусто, чего быть не может. Если  K = N = ∅,  то  A = D  и  B = C,  но это противоречит тому, что мы взяли два различных стратегических набора. Остальные случаи аналогичны.
  При закрытии первого стратегического набора закрыли все дороги, соединяющие множества K и M, K и N, L и M, L и N, и оставили открытыми дороги, соединяющие множества K с L и M с N. При закрытии второго набора закрыли все дороги, соединяющие множества K и L, K и N, L и M, M и N, и оставили открытыми дороги, соединяющие K с M и L с N.
  Итак, множество дорог, принадлежащих ровно одному стратегическому набору, – это все дороги, соединяющие K и L, K и M, L и N, M и N. При закрытии такого набора дорог множество баз распадётся по крайней мере на (непустые) множества  KN  и  LM,  не соединённые дорогами. Другими словами, мы получим важный набор, что и требовалось.

Замечания

Этот набор не обязательно будет стратегическим – пусть, например, множества K и N непусты, но из K в N не ведёт ни одной дороги.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 61
Год 1998
вариант
Класс 9
задача
Номер 4

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

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