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