Десант

Условие

В игре «Десант» две армии захватывают страну. Игроки ходят по очереди, каждым ходом занимая один из свободных городов.

Первый город захватывается с воздуха, а каждым следующим ходом можно захватить любой населенный пункт, соединенный дорогой с каким-либо городом, уже занятым этой армией.

Подсказка: вспомните строение ароматических углеводородов.

Если таких городов нет, армия прекращает боевые действия, и игрок считается проигравшим.

Постройте такую схему городов и дорог, чтобы игрок, который ходит вторым, смог захватить более половины всех городов, независимо от того, как будет действовать армия его соперника.

Ответ

Такая схема изображена на рисунке 48.

Рис. 48. Выигрышная для второго игрока схема городов и дорог

Пусть на кольце последовательно расположены точки А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 надо выбирать достаточно большим).