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

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

Условие

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


Решение

При  n = 3  очевидно выигрывает первый, а при  n = 4  – второй. Покажем, как первый выигрывает при  n > 4.  После первого хода второго игрока покрашены две соседние стороны. Первый может покрасить сторону "через одну" от них, образовав непокрашенную "дырку" из одной стороны. Это его заповедник, который второй покрасить не может. Заповедник первый использует только если у него не будет другого хода. Если такой момент наступит (второй может проиграть и раньше), то (после "закрытия" заповедника) непокрашенная часть будет состоять из пар смежных сторон. Далее первый всегда может отвечать на ход второго, закрашивая сторону из той же пары.


Ответ

Только при  n = 4.

Замечания

4 балла

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

олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант весенний тур, тренировочный вариант, 8-9 класс
Задача
Номер 2

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

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