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

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

Условие

Внутри выпуклого 100-угольника выбрана точка X, не лежащая ни на одной его стороне или диагонали. Исходно вершины многоугольника не отмечены. Петя и Вася по очереди отмечают ещё не отмеченные вершины 100-угольника, причём Петя начинает и первым ходом отмечает сразу две вершины, а далее каждый своим очередным ходом отмечает по одной вершине. Проигрывает тот, после чьего хода точка X будет лежать внутри многоугольника с отмеченными вершинами. Докажите, что Петя может выиграть, как бы ни ходил Вася.


Решение

  Раскрасим стороны 100-угольника в чёрный и белый цвета так, чтобы каждые две соседних стороны имели разные цвета. Рассмотрим две одноцветные стороны AB и CD, образующие выпуклый четырёхугольник ABCD; пусть его диагонали AC и BD пересекаются в точке K. Предположим, что точка X лежит в треугольнике KBC (рис. слева). Укажем стратегию Пети для этого случая.
  Первым ходом он выбирает вершины B и C. После этого оба игрока могут выбирать только вершины, лежащие в другой полуплоскости от прямой BC, нежели точка X. Этих вершин чётное число, поскольку они разбиваются на пары вершин, образующих стороны того же цвета, что и AB. Поэтому последний ход будет за Петей.

  Осталось показать, что такие стороны AB и CD найдутся. Пусть это не так. Рассмотрим любую вершину T. Предположим, что луч TX пересекает чёрную сторону PQ (рис. справа). Пусть TR – чёрная сторона, выходящая из T; можно считать, что TRPQ – выпуклый четырёхугольник. Если точка X лежит внутри треугольника TRQ, то требуемый четырёхугольник RTQP найден; в противном случае луч RX тоже должен пересекать отрезок PQ.
  Пусть RS – следующая за TR сторона 100-угольника. Если луч SX пересекает белую сторону, то аналогично доказывается, что луч RX также должен её пересекать, что не так. Значит, SX пересекает какую-то чёрную сторону, и можно повторить предыдущие рассуждения для вершины S. Рассуждая так и дальше, мы получим, что для каждой чёрной стороны T'R' найдётся чёрная сторона P'Q', которую пересекают оба луча T'X и R'X. Однако это неверно для чёрной стороны PQ (лучи PX и QX пересекают участки контура QT и RP соответственно). Противоречие.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 5
класс
Класс 10
задача
Номер 10.4

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

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