ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109769
Темы:    [ Степень вершины ]
[ Связность и разложение на связные компоненты ]
[ Правило произведения ]
Сложность: 5
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Лифшиц Ю.

Гидры состоят из голов и шей (каждая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы 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.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2002
Этап
Вариант 5
Класс
Класс 9
задача
Номер 02.5.9.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .