Разделы 
Дополнительно
Задача по математике - 1715
2019-01-20 
В некотором государстве было 2004 города, соединенных дорогами так, что из любого города можно было добраться до любого другого. Известно, что при запрещенном проезде по любой из дорог, по-прежнему из любого города можно было добраться до любого другого. Министр транспорта и министр внутренних дел по очереди вводят на дорогах, пока есть возможность, одностороннее движение (на одной дороге за ход), причем министр, после хода которого из какого-либо города стало невозможно добраться до какого-либо другого, немедленно уходит в отставку. Первым ходит министр транспорта. Может ли кто-либо из министров добиться отставки другого независимо от его игры?
Решение:
Построим ориентированный граф, вершины которого соответствуют городам, а ребра - дорогам, причем дорогам с односторонним движением мы поставим в соответствия ориентированные, а дорогам с двусторонним движением - неориентированные ребра.
Докажем, что в любой момент игры любое еще не ориентированное ребро можно ориентировать так, чтобы связность графа сохранилась. Из этого очевидно следует, что при правильной игре обоих игроков игра закончится вничью, и оба министра сохранят свои посты.
Итак, пусть ребро между вершинами $u$ и $v$ еще не ориентированно. Заметим, что если между этими вершинами существует путь (не умаляя общности можно считать, что он ведет от $u$ к $v$), не проходящий по данному ребру, то ребро $(u, v)$ можно ориентировать в направлении от v к и. Тогда в любом пути, проходившем по данному ребру в противоположном направлении, мы можем заменить это ребро на указанный выше путь от и к v, и связность графа не нарушится.
Таким образом, нам достаточно рассмотреть ситуацию, когда между вершинами $u$ и $v$ не существует пути, не проходящего через ребро $(u, v)$. Рассмотрим множество $U$ всех вершин, до которых можно добраться из вершины $u$, не проходя по ребру $(u, v)$ (включая и саму вершину $u$). Поскольку граф связен, для любой вершины множества $U$ должен существовать путь, ведущий от нее до вершины $v$. Однако, по нашему предположению, этот путь обязан проходить по ребру $(u, v)$. Из этого следует, что из любой вершины множества $U$ можно добраться до вершины и, не проходя по ребру $(u, v)$. Но тогда из любой вершины множества $U$ можно добраться до любой другой вершины этого множества, не проходя по ребру $(u, v)$.
Аналогичное множество для вершины $v$ мы обозначим через $V$. Легко видеть, что из любой его вершины также можно добраться до любой другой его вершины, не проходя по ребру $(u, v)$.
Поскольку граф связен, любая вершина должна принадлежать ровно одному из множеств $U$ или $V$. Кроме того, поскольку исходный граф, в котором ребра не были ориентированы, сохранял связность при удалении ребра $(u, v)$, между множествами $U$ и $V$ должно существовать еще хотя бы одно ребро, кроме ребра $(u, v)$. Пусть это ребро ведет из вершины $u_1 \in U$ в вершину $v_1 \in V$ (в данный момент игры это ребро может быть как ориентированным, так и неориентированным, но как минимум в одном из направлений, например, из $u$ в $v_1$, по нему пройти в любом случае можно). Но тогда из вершины $u$ мы можем добраться до вершины $u_1$, из $u_1 до v_1$ и из $v_1$ до $v$, не проходя при этом по ребру $(u, v)$, что противоречит сделанному ранее предположению. Полученное противоречие завершает решение задачи.
Ответ. Не сможет ни один из них.
В некотором государстве было 2004 города, соединенных дорогами так, что из любого города можно было добраться до любого другого. Известно, что при запрещенном проезде по любой из дорог, по-прежнему из любого города можно было добраться до любого другого. Министр транспорта и министр внутренних дел по очереди вводят на дорогах, пока есть возможность, одностороннее движение (на одной дороге за ход), причем министр, после хода которого из какого-либо города стало невозможно добраться до какого-либо другого, немедленно уходит в отставку. Первым ходит министр транспорта. Может ли кто-либо из министров добиться отставки другого независимо от его игры?
Решение:
Построим ориентированный граф, вершины которого соответствуют городам, а ребра - дорогам, причем дорогам с односторонним движением мы поставим в соответствия ориентированные, а дорогам с двусторонним движением - неориентированные ребра.
Докажем, что в любой момент игры любое еще не ориентированное ребро можно ориентировать так, чтобы связность графа сохранилась. Из этого очевидно следует, что при правильной игре обоих игроков игра закончится вничью, и оба министра сохранят свои посты.
Итак, пусть ребро между вершинами $u$ и $v$ еще не ориентированно. Заметим, что если между этими вершинами существует путь (не умаляя общности можно считать, что он ведет от $u$ к $v$), не проходящий по данному ребру, то ребро $(u, v)$ можно ориентировать в направлении от v к и. Тогда в любом пути, проходившем по данному ребру в противоположном направлении, мы можем заменить это ребро на указанный выше путь от и к v, и связность графа не нарушится.
Таким образом, нам достаточно рассмотреть ситуацию, когда между вершинами $u$ и $v$ не существует пути, не проходящего через ребро $(u, v)$. Рассмотрим множество $U$ всех вершин, до которых можно добраться из вершины $u$, не проходя по ребру $(u, v)$ (включая и саму вершину $u$). Поскольку граф связен, для любой вершины множества $U$ должен существовать путь, ведущий от нее до вершины $v$. Однако, по нашему предположению, этот путь обязан проходить по ребру $(u, v)$. Из этого следует, что из любой вершины множества $U$ можно добраться до вершины и, не проходя по ребру $(u, v)$. Но тогда из любой вершины множества $U$ можно добраться до любой другой вершины этого множества, не проходя по ребру $(u, v)$.
Аналогичное множество для вершины $v$ мы обозначим через $V$. Легко видеть, что из любой его вершины также можно добраться до любой другой его вершины, не проходя по ребру $(u, v)$.
Поскольку граф связен, любая вершина должна принадлежать ровно одному из множеств $U$ или $V$. Кроме того, поскольку исходный граф, в котором ребра не были ориентированы, сохранял связность при удалении ребра $(u, v)$, между множествами $U$ и $V$ должно существовать еще хотя бы одно ребро, кроме ребра $(u, v)$. Пусть это ребро ведет из вершины $u_1 \in U$ в вершину $v_1 \in V$ (в данный момент игры это ребро может быть как ориентированным, так и неориентированным, но как минимум в одном из направлений, например, из $u$ в $v_1$, по нему пройти в любом случае можно). Но тогда из вершины $u$ мы можем добраться до вершины $u_1$, из $u_1 до v_1$ и из $v_1$ до $v$, не проходя при этом по ребру $(u, v)$, что противоречит сделанному ранее предположению. Полученное противоречие завершает решение задачи.
Ответ. Не сможет ни один из них.
