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

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

Условие

На столе лежат  N > 2  кучек по одному ореху в каждой. Двое ходят по очереди. За ход нужно выбрать две кучки, где числа орехов взаимно просты, и объединить эти кучки в одну. Выиграет тот, кто сделает последний ход. Для каждого N выясните, кто из играющих может всегда выигрывать, как бы ни играл его противник.


Решение

Назовём плохими позиции вида  (2n + 1, 1, ..., 1)  (единиц больше одной). Исходная позиция – плохая. Первый из плохой позиции может перейти либо в
(2n + 2, 1, ..., 1),  либо в  (2n + 1, 2, 1, ..., 1);  в обоих случаях второй может снова "загнать" первого в плохую позицию  (2n + 3, 1, ..., 1).  В случае нечётного N второй придерживается такой стратегии до конца, а в случае чётного – до позиции  (N – 3, 1, 1, 1),  после чего на любой ход первого
(в  (N – 2, 1, 1)  или в  (N – 3, 2, 1))  отвечает ходом в  (N – 2, 2).


Ответ

Второй игрок.

Замечания

6 баллов

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

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

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

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