Разделы 
Дополнительно
Задача по математике - 3273
2019-05-29 
В стране Нашии есть военные базы, соединенные дорогами. Набор дорог называется важным, если после закрытия этих дорог найдутся две базы, не соединенные путем. Важный набор называется стратегическим, если он не содержит меньшего важного набора. Докажите, что множество дорог, каждая из которых принадлежит ровно одному из двух различных стратегических наборов, образует важный набор.
Решение:
Из любой базы можно попасть на любую, иначе пустое множество образует важный набор, но тогда пустое множество - это единственный стратегический набор, а в условии задачи говорится про два различных стратегических набора.
Рассмотрим некоторый стратегический набор.
Лемма. При закрытии всех дорог этого набора множество баз распадается ровно на две не соединенные друг с другом части, причем ни одна из дорог внутри каждой из этих частей не будет закрыта.
Доказательство. Будем говорить, что две базы лежат в одной компоненте связности, если из одной базы можно проехать на другую. После закрытия стратегического набора множество всех баз разобьется на компоненты связности: при этом из баз, находящихся в одной компоненте, можно будет проехать друг в друга, а из баз, лежащих в разных компонентах, - нельзя (см. факт 3). Так как набор важный, этих компонент не менее двух.
Докажем, что их ровно две. Пусть их хотя бы три. Рассмотрим любую (закрытую) дорогу $a$, ведущую из одной компоненты связности $X$ в другую компоненту $Y$ (такая дорога найдется, так как до закрытия можно было проехать из любой базы на любую). Пусть $Z$ - третья компонента связности. Удалим дорогу a из нашего стратегического набора (т. е. не будем ее закрывать), тогда получится снова важный набор, так как из компоненты $X$ в компоненту $Z$ нельзя проехать, даже пользуясь дорогой $a$. Но тогда наш набор - не стратегический. Это противоречие показывает, что компонент связности ровно две.
Рассмотрим любую дорогу внутри одной из компонент связности. Если она закрыта, то, как и выше, выкинем ее из стратегического набора. Останется важный набор - противоречие. Лемма доказана.
Пусть первый стратегический набор разбивает множество баз на подмножества $A$ и $B$, а второй - на $C$ и $D$.
Пусть $K = A \cap C, L = A \cap D, M = B \cap C, N = B \cap D$ (рис.). Множества $K, L, M, N$ попарно не пересекаются, а их объединение - это множество всех баз. Докажем, что пустым может быть только одно из них (или ни одного). Действительно, если $K = L = \varnothing$, то $A$ пусто, чего быть не может. Если $K = N = \varnothing$, то $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$ \cup $N$ и $L$ \cup $M$, не соединенные дорогами. Другими словами, мы получим важный набор, что и требовалось доказать.
В стране Нашии есть военные базы, соединенные дорогами. Набор дорог называется важным, если после закрытия этих дорог найдутся две базы, не соединенные путем. Важный набор называется стратегическим, если он не содержит меньшего важного набора. Докажите, что множество дорог, каждая из которых принадлежит ровно одному из двух различных стратегических наборов, образует важный набор.
Решение:
Из любой базы можно попасть на любую, иначе пустое множество образует важный набор, но тогда пустое множество - это единственный стратегический набор, а в условии задачи говорится про два различных стратегических набора.
Рассмотрим некоторый стратегический набор.
Лемма. При закрытии всех дорог этого набора множество баз распадается ровно на две не соединенные друг с другом части, причем ни одна из дорог внутри каждой из этих частей не будет закрыта.
Доказательство. Будем говорить, что две базы лежат в одной компоненте связности, если из одной базы можно проехать на другую. После закрытия стратегического набора множество всех баз разобьется на компоненты связности: при этом из баз, находящихся в одной компоненте, можно будет проехать друг в друга, а из баз, лежащих в разных компонентах, - нельзя (см. факт 3). Так как набор важный, этих компонент не менее двух.
Докажем, что их ровно две. Пусть их хотя бы три. Рассмотрим любую (закрытую) дорогу $a$, ведущую из одной компоненты связности $X$ в другую компоненту $Y$ (такая дорога найдется, так как до закрытия можно было проехать из любой базы на любую). Пусть $Z$ - третья компонента связности. Удалим дорогу a из нашего стратегического набора (т. е. не будем ее закрывать), тогда получится снова важный набор, так как из компоненты $X$ в компоненту $Z$ нельзя проехать, даже пользуясь дорогой $a$. Но тогда наш набор - не стратегический. Это противоречие показывает, что компонент связности ровно две.
Рассмотрим любую дорогу внутри одной из компонент связности. Если она закрыта, то, как и выше, выкинем ее из стратегического набора. Останется важный набор - противоречие. Лемма доказана.
Пусть первый стратегический набор разбивает множество баз на подмножества $A$ и $B$, а второй - на $C$ и $D$.
Пусть $K = A \cap C, L = A \cap D, M = B \cap C, N = B \cap D$ (рис.). Множества $K, L, M, N$ попарно не пересекаются, а их объединение - это множество всех баз. Докажем, что пустым может быть только одно из них (или ни одного). Действительно, если $K = L = \varnothing$, то $A$ пусто, чего быть не может. Если $K = N = \varnothing$, то $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$ \cup $N$ и $L$ \cup $M$, не соединенные дорогами. Другими словами, мы получим важный набор, что и требовалось доказать.
