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

Проект МЦНМО
при участии
школы 57
Задача 116777
Темы:    [ Теория игр (прочее) ]
[ Правильные многоугольники ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

Автор: Ивлев Ф.

На окружности отмечено 2n + 1  точек, делящих её на равные дуги  (n ≥ 2).  Двое по очереди стирают по одной точке. Если после хода игрока все треугольники с вершинами в ещё отмеченных точках – тупоугольные, он выигрывает, и игра заканчивается. Кто выиграет при правильной игре: начинающий игру или его противник?


Решение

  Приведём выигрышную стратегию второго игрока. Он будет добиваться выполнения следующего условия: если после его хода осталось  2k + 1 ≥ 5  точек, то на любой полуокружности осталось не менее k отмеченных точек.
  В начале игры это условие выполнено. Пусть перед каким-то ходом первого оно выполнено; пронумеруем оставшиеся точки по порядку
A0, ..., A2k.  Пусть для определённости первый своим ходом удаляет точку A0. Треугольник Ak+1A1Ak+2 остроугольный, так что игра ещё не закончилась. Второму достаточно удалить точку Ak. Теперь, если с некоторой полуокружности удалено не более одной точки, то на ней осталось не менее  k – 1  точки; иначе с неё стёрты точки A0 и Ak, поэтому на ней остались либо точки  A1, ..., Ak–1,  либо точки Ak+1, ..., A2k;  в любом случае для неё требуемое условие выполнено.
  Итак, если первый не проиграет раньше, то после  2n – 4  ходов на доске останется пять точек  A0, A1, A2, A3, A4.  Пусть для определённости первый удалит точку A0; тогда ещё останется остроугольный треугольник A1A3A4. Второй же последним ходом удалит A4. Оставшийся треугольник A1A2A3 будет тупоугольным (иначе нашлась бы полуокружность, содержащая из пяти точек лишь A2), то есть второй выиграет.


Ответ

Противник.

Замечания

Ту же стратегию можно оформить по-другому. Соединим каждую из исходных точек с двумя наиболее удалёнными от неё. Все проведённые отрезки образуют (2n+1)-звенную ломаную. Второй может ходить так, чтобы после каждого его хода (кроме последнего) все стёртые точки разбивались на пары точек, соединённых отрезком.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 5
класс
Класс 11
Задача
Номер 11.7

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

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