Олимпиадная задача о стратегии в крестиках-ноликах 10×10 — Теория алгоритмов, 6-8 класс
Задача
Двое играют в крестики-нолики на доске 10×10 по следующим правилам. Сначала они заполняют крестиками и ноликами всю доску, ставя их по очереди (начинающий игру ставит крестики, его партнер – нолики). Затем подсчитываются два числа: K – число пятерок подряд стоящих крестиков и H – число пятерок подряд стоящих ноликов. (Считаются пятерки, стоящие по горизонтали, по вертикали и параллельно диагонали; если подряд стоят шесть крестиков, то это даёт две пятерки, если семь, то три и т. д.) Число K – H считается выигрышем первого игрока (проигрышем второго).
а) Существует ли у первого игрока беспроигрышная стратегия?
б) Существует ли у него выигрышная стратегия?
Решение
б) У второго игрока есть беспроигрышная стратегия. Она состоит в том, что на каждый ход первого нужно ставить нолик в клетку, симметричную относительно центра доски клетке, в которую только что был поставлен крестик. Тогда к концу игры количество пятёрок подряд стоящих крестиков будет в точности равно количеству пятёрок подряд стоящих ноликов. а) Вот беспроигрышная стратегия первого игрока. Первый ход произвольный. Далее, если второй игрок ходит симметрично (ставит нолик в клетку, симметричную клетке, в которую только что поставлен крестик), то первый игрок снова ставит крестик в произвольную клетку. Если второй игрок ходит не симметрично (обозначим клетку, симметричную последнему поставленному крестику, через A), первый игрок перехватывает "симметричную" стратегию и ставит крестики в клетки, симметричные тем, в которые второй ставит нолики, до тех пор, пока второй не поставит нолик в клетку A.
Ответ
а) Существует; б) не существует.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь