|
|
 |
Условие
На столе лежат 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 баллов
