Задача
Дана клетчатая полоса 1×N. Двое играют в следующую игру. На очередном ходу первый игрок ставит в одну из свободных клеток крестик, а второй – нолик. Не разрешается ставить в соседние клетки два крестика или два нолика. Проигрывает тот, кто не может сделать ход.
Кто из игроков может всегда выиграть (как бы ни играл его соперник)?
Решение
Пусть N > 1. Приведём выигрышную стратегию второго игрока. Первый ход он делает в крайнюю клетку, а дальше ходит как угодно. После k-го хода первого игрока крестики делят полоску не менее чем на k частей, состоящих из пустых клеток и ноликов. Но к этому моменту выставлен лишь k – 1 нолик, значит, в одной из частей нолика нет, и туда второй игрок может сделать ход. Так как игра когда-нибудь кончится, проиграет первый.
Ответ
При N = 1 выигрывает первый игрок, при N > 1 – второй.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь