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