|
|
 |
Условие
Дано целое число n > 1. Двое игроков по очереди отмечают точки на окружности: первый – красным цветом, второй – синим (отмечать одну и ту же точку дважды нельзя). Когда отмечено по n точек каждого цвета, игра заканчивается. После этого каждый игрок находит на окружности дугу наибольшей длины с концами своего цвета, на которой больше нет отмеченных точек. Игрок, у которого найденная длина больше, выиграл (в случае равенства длин дуг, а также при отсутствии таких дуг у обоих игроков – ничья). Кто из играющих может всегда выигрывать, как бы ни играл противник?
Решение
Приведём выигрышную стратегию Второго игрока. Можно считать, что длина окружности равна n и Первый сначала отметил вершину вписанного правильного n-угольника. Второй отмечает вершины этого многоугольника, пока это возможно. Назовём дуги, соединяющие соседние вершины n-угольника, основными; основную дугу без внутренних отмеченных точек назовём чистой, а чистую дугу с красными концами – опасной. Пусть к моменту, когда вершины "кончатся", Первый отметил k вершин, а Второй n – k (значит, у него осталось k ходов). В этот момент опасных дуг не более k – 1, поэтому за k – 1 ход Второй успеет их обезопасить. В результате перед последним ходом Второго все дуги с красными концами короче 1; пусть максимальная длина такой дуги равна l < 1. Заметим, что осталась чистая дуга (изначально их было n, а не в вершины был сделан только n – 1 ход). У неё есть синий конец, и Второй может отметить на ней точку, находящуюся от синего конца на расстоянии, большем l.
Ответ
Второй игрок.
Замечания
1. Идеология. У Второго есть простая стратегия, гарантирующая ничью: каждый раз отмечать точку, симметричную ходу
первого относительно центра окружности. Следовательно, искать
выигрышную стратегию для Первого бесполезно.
Рассмотрим случай n = 2. Если Первый отметит две диаметрально противоположные точки, он обеспечит себе, как минимум, ничью. Действительно, если синие точки окажутся на разных
полуокружностях, то получится ничья, а если в одной – значит, выиграл
Первый. Следовательно, Второй первым своим ходом должен выбрать точку,
диаметрально противоположную точке Первого. После этого Первый отмечает точку на одной из полученных полуокружностей (получая таким образом дугу длины l < 1). Теперь Второй отмечает точку на другой половине окружности так, чтобы получилась дуга длины L > l, и выигрывает.
Нам надо найти правильный аналог этой стратегии для n > 2. Если дать Первому отметить все вершины некоторого правильного
n-угольника, то по аналогичным причинам больше, чем на ничью, рассчитывать нельзя. Следовательно, хотя бы раз надо отметить какую-нибудь вершину правильного n-угольника, в одну из вершин которого был сделан первый ход Первого. После этого вышеприведённое решение уже напрашивается.
2. 9 баллов.
