Задача 34924

Темы:    [ Теория игр (прочее) ] [ Разбиения на пары и группы; биекции ]

Сложность: 3 Классы:

Условие

На шахматной доске стоит фишка. Двое по очереди передвигают фишку на соседнюю по стороне клетку. При этом запрещается ставить фишку на поле, где она уже побывала. Проигрывает тот, кто не может сделать очередной ход. Кто выигрывает при правильной игре?

Подсказка

Поставьте в соответствие ходу второго некоторый ход первого.

Решение

Разобьём доску на доминошки 1×2. Стратегия первого: если перед ходом первого фишка стоит в одной из клеток, принадлежащих какой-то доминошке, то своим ходом первый игрок передвигает её в другую клетку этой же доминошки. Заметим, что после хода первого все разрешённые клетки снова разбиты на доминошки. Это означает, что первый игрок всегда сможет сделать ход, придерживась своей стратегии, и следовательно, не проиграет.

Ответ

Первый.

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

web-сайт

задача