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