Разделы 
Дополнительно
Задача по математике - 1970
2019-01-22 
Гидры состоят из голов и шей (любая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы $A$ гидры. Но при этом из головы $A$ мгновенно вырастает по одной шее во все головы, с которыми $A$ не была соединена. Геракл побеждает гидру, если ему удастся разрубить ее на две несвязанные шеями части. Найдите наименьшее $N$, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более, чем $N$ ударов.
Решение:
Перейдем к графу, в котором головы - вершины, шеи - ребра, а удар по шеям, выходящим из головы A назовем инвертированием вершины $A$. Тогда если есть вершина $X$ степени не больше 10, то достаточно инвертировать ее соседей, и она отделится, т. е. эта вершина не будет соединена с остальными вершинами графа. Если есть вершина, соединенная со всеми вершинами, за исключением $n (n \leq 9)$, то нужно инвертировать сначала эту вершину, а затем те $n$ вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится. Если же для каждой вершины есть хотя бы 11 вершин, соединенных с ней, и хотя бы 10, не соединенных с ней, то всего вершин не меньше 22, и ребер не меньше $\frac{22 \cdot 11}{2} > 100$.
Приведем пример гидры, которую нельзя разрубить за 9 ударов: две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп. Заметим, что состояние ребра между вершинами A и B не изменилось (т. е. оно осталось, если было вначале, и не появилось, - иначе) тогда и только тогда, когда вершины $A$ и $B$ отрубали в сумме четное число раз. Поэтому порядок отрубания вершин неважен, и бессмысленно отрубать вершину два раза.
Пусть по нашей гидре нанесено не более 9 ударов. Тогда в каждой группе осталось по неотрубленной голове, и поэтому есть шея из одной группы в другую; более того, все неотрубленные головы образуют связное множество. С другой стороны, каждая неотрубленная голова связана со всеми отрубленными в своей группе. Поэтому, если в каждой части отрублено хотя бы по голове, то гидра осталась связной. Если же все отрубленные головы в одной части, то гидра тоже осталась связной: любая неотрубленная голова в этой части связана со всей другой частью и со всеми отрубленными.
Ответ. 10.
Гидры состоят из голов и шей (любая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы $A$ гидры. Но при этом из головы $A$ мгновенно вырастает по одной шее во все головы, с которыми $A$ не была соединена. Геракл побеждает гидру, если ему удастся разрубить ее на две несвязанные шеями части. Найдите наименьшее $N$, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более, чем $N$ ударов.
Решение:
Перейдем к графу, в котором головы - вершины, шеи - ребра, а удар по шеям, выходящим из головы A назовем инвертированием вершины $A$. Тогда если есть вершина $X$ степени не больше 10, то достаточно инвертировать ее соседей, и она отделится, т. е. эта вершина не будет соединена с остальными вершинами графа. Если есть вершина, соединенная со всеми вершинами, за исключением $n (n \leq 9)$, то нужно инвертировать сначала эту вершину, а затем те $n$ вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится. Если же для каждой вершины есть хотя бы 11 вершин, соединенных с ней, и хотя бы 10, не соединенных с ней, то всего вершин не меньше 22, и ребер не меньше $\frac{22 \cdot 11}{2} > 100$.
Приведем пример гидры, которую нельзя разрубить за 9 ударов: две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп. Заметим, что состояние ребра между вершинами A и B не изменилось (т. е. оно осталось, если было вначале, и не появилось, - иначе) тогда и только тогда, когда вершины $A$ и $B$ отрубали в сумме четное число раз. Поэтому порядок отрубания вершин неважен, и бессмысленно отрубать вершину два раза.
Пусть по нашей гидре нанесено не более 9 ударов. Тогда в каждой группе осталось по неотрубленной голове, и поэтому есть шея из одной группы в другую; более того, все неотрубленные головы образуют связное множество. С другой стороны, каждая неотрубленная голова связана со всеми отрубленными в своей группе. Поэтому, если в каждой части отрублено хотя бы по голове, то гидра осталась связной. Если же все отрубленные головы в одной части, то гидра тоже осталась связной: любая неотрубленная голова в этой части связана со всей другой частью и со всеми отрубленными.
Ответ. 10.
