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