ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 105113
УсловиеВ игре "Десант" две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.) РешениеРассмотрим страну, карта которой изображена на рисунке (точки – города, отрезки – дороги). Так как после прекращения боевых действий вторая армия занимает хотя бы две точки Ai, первая занимает не более k + 3 точек. Поэтому доля городов, захваченных второй армией, не менее ОтветНайдётся. ЗамечанияВместо ½ можно взять любое число α < ⅔ : Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |