Олимпиадная задача про Геракла и гидру: графы и комбинаторика для 8-10 класса

  Перейдём к графу, в котором головы – вершины, шеи – ребра, а удар по шеям, выходящим из головы A назовём инвертированием вершины A.

  Если есть вершина X степени не больше 10, то достаточно инвертировать её соседей, и она отделится. Если есть вершина, соединённая со всеми вершинами, за исключением n  (n ≤ 9),  то нужно инвертировать сначала эту вершину, а затем те n вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится.

  Если же каждая вершина соединена хотя бы с 11 и не соединена хотя бы с 10 другими, то всего вершин не меньше 22, и ребер не меньше  22·11 : 2 > 100.

  Пример гидры, которую нельзя разрубить за девять ударов: две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп.

  Заметим, что состояние ребра между вершинами A и B не меняется тогда и только тогда, когда вершины A и B инвертированы в сумме чётное число раз. Поэтому порядок отрубания вершин не важен и бессмысленно инвертировать вершину дважды.

  Пусть по нашей гидре нанесено не более девяти ударов. Тогда в каждой группе осталось по неинвертированной голове, и поэтому есть шея из одной группы в другую; более того, все неинвертированные головы образуют связное множество. С другой стороны, каждая неинвертированная голова связана со всеми инвертированными в своей группе. Поэтому, если в каждой части инвертировано хотя бы по одной голове, то гидра осталась связной. Если же все инвертированные головы в одной части, то гидра тоже осталась связной: каждая неинвертированная голова в этой части связана со всей другой частью и со всеми инвертированными.

N = 10.