Олимпиадная задача "Десант": графы, множества и алгоритмы для 8–10 классов
В игре "Десант" две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.)
Показать ответ
Найдётся.
Разобрать решение
Рассмотрим страну, карта которой изображена на рисунке (точки – города, отрезки – дороги).
Покажем, что второй армии всегда удастся захватить хотя бы две точкиAi. Действительно, если первая армия первым ходом занимает точку на "ветке" изkточек, вторая армия должна занять соответствующую этой "ветке" точкуAi; если первая занимаетAi, то вторая –Bi; если первая выбирает точкуBi, то вторая – одну из точекAj, соединённую отрезком сBi. Дальнейшие действия очевидны.
Так как после прекращения боевых действий вторая армия занимает хотя бы две точкиAi, первая занимает не более k+ 3 точек. Поэтому доля городов, захваченных второй армией, не менее 
Обсуждение
0Комментариев пока нет.