2019-04-01
В игре «Десант» две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает свои боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.)
Решение:
Рассмотрим страну, карта которой изображена на рис. (точки — города, отрезки — дороги). Покажем, что второй армии всегда удастся захватить хотя бы два города $A_i$;. Действительно, если первая армия первым ходом занимает город на одной из «веток», вторая армия должна занять соответствующий этой «ветке» город $A_i$; если первая армия занимает $A_i$, то вторая — $B_i$; если первая выбирает город $B_i$, то вторая — один из городов $A_j$, соединённый дорогой с $B_i$. Дальнейшие действия очевидны.
Итак, после прекращения боевых действий вторая армия занимает хотя бы два города $A_i$, а значит, и две соответствующие «ветки», и город $B_j$ между занятыми городами $A_{i}$, всего по крайней мере $2k+ 3$ городов. Поэтому доля городов, захваченных второй армией, не менее $\frac {2k+3}{3k+6}$. Уже при $k = 1$ это число больше. Заметим, что в условии задачи вместо доли можно взять любое число $а < \frac{2}{3}$, поскольку $\frac {2k+3}{3k+6} > a$ при достаточно больших $k$.
Ответ: да, найдётся.