ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111916
Темы:    [ Теория игр (прочее) ]
[ Правильные многоугольники ]
[ Разбиения на пары и группы; биекции ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Дано целое число  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 баллов.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 72
Год 2009
класс
Класс 9
задача
Номер 6
олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .