Олимпиадная задача по теории множеств и графов для 8–10 классов от Скопенкова

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

  Рассмотрим некоторый стратегический набор.   Лемма. При закрытии всех дорог этого набора граф баз распадается ровно на две компоненты связности, причём ни одна из дорог внутри каждой из этих частей не будет закрыта.

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

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

  Рассмотрим любую дорогу внутри одной из компонент связности. Если она закрыта, то, как и выше, выкинем её из стратегического набора. Останется важный набор – противоречие.

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

M = B ∩ C,  N = B ∩ D  (см. рис.).

  Множества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. При закрытии такого набора дорог множество баз распадётся по крайней мере на (непустые) множества  K∪N  и  L∪M,  не соединённые дорогами. Другими словами, мы получим важный набор, что и требовалось.

Ответ задачи отсутствует