Задача 105113

Темы:    [ Теория игр (прочее) ] [ Планарные графы. Формула Эйлера ] [ Необычные конструкции ]

Сложность: 4- Классы: 8,9,10

Условие

Авторы: Шаповалов А.В., Грозман П.Я., Шаповалов Д.А.

В игре "Десант" две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.)

Решение

  Рассмотрим страну, карта которой изображена на рисунке (точки – города, отрезки – дороги).

  Покажем, что второй армии всегда удастся захватить хотя бы две точки A_i. Действительно, если первая армия первым ходом занимает точку на "ветке" из k точек, вторая армия должна занять соответствующую этой "ветке" точку A_i; если первая занимает A_i, то вторая – B_i; если первая выбирает точку B_i, то вторая – одну из точек A_j, соединённую отрезком с B_i. Дальнейшие действия очевидны.
  Так как после прекращения боевых действий вторая армия занимает хотя бы две точки A_i, первая занимает не более  k + 3  точек. Поэтому доля городов, захваченных второй армией, не менее  

Ответ

Найдётся.

Замечания

Вместо ½ можно взять любое число  α < ⅔ :     при достаточно больших k.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	64
Год	2001
вариант
Класс	10
задача
Номер	6