Question

В игре «Десант» две армии захватывают страну. Игроки ходят по очереди, каждым ходом занимая один из свободных городов. Первый город захватывается с воздуха, а каждым следующим ходом можно захватить любой населенный пункт, соединенный дорогой с каким-либо городом, уже занятым этой армией. Если таких городов нет, армия прекращает боевые действия, и игрок считается проигравшим.
Постройте такую схему городов и дорог, чтобы игрок, который ходит вторым, смог захватить более половины всех городов, независимо от того, как будет действовать армия его соперника.

Answer 1

Ответ
Пусть на кольце последовательно расположены точки А1, В2, А3, В1, А2, В3, причем от точек А1, А3, А2 отходят «ветки» с N городами в каждой.
Если первый игрок первым ходом занимает точку на ветке, армия второго игрока должна занять соответствующую точку Аi.
Если первая армия первым ходом занимает точку Ai, то вторая – Bi.
Если первый игрок первым ходом занимает точку Bi, то второй – любую из точек Aj (j не равно i). Дальнейшие действия очевидны. Поскольку в конце игры вторая армия занимает хотя бы две точки Ai, первый игрок захватывает не более, чем n + 3 точек. Поэтому доля городов, захваченных армией второго игрока, не менее (2n + 3)/(3n + 6) > 1/2.
В условии задачи вместо 1/2 можно взять любое число, меньшее 2/3 (в этом случае N надо выбирать достаточно большим).