|
|
 |
Условие
Гидры состоят из голов и шей (каждая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы A гидры. Но при этом из головы A мгновенно вырастает по одной шее во все головы, с которыми A не была соединена. Геракл побеждает гидру, если ему удастся разрубить её на две несвязанные шеями части. Найдите наименьшее N, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более чем N ударов.
Решение
Перейдём к графу, в котором головы – вершины, шеи – ребра, а удар по шеям, выходящим из головы A назовём инвертированием вершины A.
Если есть вершина X степени не больше 10, то достаточно инвертировать её соседей, и она отделится. Если есть вершина, соединённая со всеми вершинами, за исключением n (n ≤ 9), то нужно инвертировать сначала эту вершину, а затем те n вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится.
Если же каждая вершина соединена хотя бы с 11 и не соединена хотя бы с 10 другими, то всего вершин не меньше 22, и ребер не меньше 22·11 : 2 > 100.
Пример гидры, которую нельзя разрубить за девять ударов: две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп.
Заметим, что состояние ребра между вершинами A и B не меняется тогда и только тогда, когда вершины A и B инвертированы в сумме чётное число раз. Поэтому порядок отрубания вершин не важен и бессмысленно инвертировать вершину дважды.
Пусть по нашей гидре нанесено не более девяти ударов. Тогда в каждой группе осталось по неинвертированной голове, и поэтому есть шея из одной группы в другую; более того, все неинвертированные головы образуют связное множество. С другой стороны, каждая неинвертированная голова связана со всеми инвертированными в своей группе. Поэтому, если в каждой части инвертировано хотя бы по одной голове, то гидра осталась связной. Если же все инвертированные головы в одной части, то гидра тоже осталась связной: каждая неинвертированная голова в этой части связана со всей другой частью и со всеми инвертированными.
Ответ
N = 10.
