Разделы 
Дополнительно
Задача по математике - 3123
2019-05-19 
Вырезать из клетчатой бумаги многоугольник наименьшей площади такой, что, играя на нем в крестики - нолики - три (КН-3), начинающий всегда выигрывает. КН-3 - игра в «крестики - нолики», когда выигрывает тот, кто первым поставит три значка - крестика или нолика - подряд на одной прямой.
Игры
Решение:
При $n = 7$ многоугольник, на котором выигрывает первый, существует (рис.). Вначале первый игрок ставит крестик в клетку $a$. При любом ответном ходе второго игрока либо горизонтальная, либо вертикальная полоса свободна от нулей; будем считать, что нулей нет на-горизонтали. Тогда вторым своим ходом первый игрок ставит крестик в клетку $b$ и, очевидно, выигрывает, как бы ни пошел второй игрок.
Покажем, что при $n \leq 6$ искомого многоугольника не существует.
I случай. Никакие четыре клетки подряд не лежат на одной прямой.
В этом случае после двух ходов первого игрока остается разве лишь одна клетка, такая, что, поставив в нее крестик, первый может выиграть. Вторым своим ходом второй игрок ставит в эту клетку нулик - и первый не выигрывает.
II случай. Найдутся четыре клетки подряд, лежащие нa одной прямой.
Если на этой прямой найдется еще хотя бы одна клетка, то поставить три крестика можно только на этой прямой, и, очевидно, при правильной игре второго первый не выигрывает.
Пусть на этой прямой нет пятой клетки.
Стратегия второго игрока.
На любой крестик, поставленный на «прямую четырех клеток», второй игрок отвечает постановкой нулика на свободную клетку той же прямой (если таковая имеется). Если прямая заполнена, то второй игрок ходит произвольным образом.
На любой крестик, поставленный вне этой прямой, второй игрок отвечает постановкой нулика на свободную клетку вне этой прямой {если таковая имеется). Если ее нет, то второй ходит произвольным образом.
Ясно, что при такой стратегии второго игрока первый не выиграет.
Вырезать из клетчатой бумаги многоугольник наименьшей площади такой, что, играя на нем в крестики - нолики - три (КН-3), начинающий всегда выигрывает. КН-3 - игра в «крестики - нолики», когда выигрывает тот, кто первым поставит три значка - крестика или нолика - подряд на одной прямой.
Игры
Решение:
При $n = 7$ многоугольник, на котором выигрывает первый, существует (рис.). Вначале первый игрок ставит крестик в клетку $a$. При любом ответном ходе второго игрока либо горизонтальная, либо вертикальная полоса свободна от нулей; будем считать, что нулей нет на-горизонтали. Тогда вторым своим ходом первый игрок ставит крестик в клетку $b$ и, очевидно, выигрывает, как бы ни пошел второй игрок.
Покажем, что при $n \leq 6$ искомого многоугольника не существует.
I случай. Никакие четыре клетки подряд не лежат на одной прямой.
В этом случае после двух ходов первого игрока остается разве лишь одна клетка, такая, что, поставив в нее крестик, первый может выиграть. Вторым своим ходом второй игрок ставит в эту клетку нулик - и первый не выигрывает.
II случай. Найдутся четыре клетки подряд, лежащие нa одной прямой.
Если на этой прямой найдется еще хотя бы одна клетка, то поставить три крестика можно только на этой прямой, и, очевидно, при правильной игре второго первый не выигрывает.
Пусть на этой прямой нет пятой клетки.
Стратегия второго игрока.
На любой крестик, поставленный на «прямую четырех клеток», второй игрок отвечает постановкой нулика на свободную клетку той же прямой (если таковая имеется). Если прямая заполнена, то второй игрок ходит произвольным образом.
На любой крестик, поставленный вне этой прямой, второй игрок отвечает постановкой нулика на свободную клетку вне этой прямой {если таковая имеется). Если ее нет, то второй ходит произвольным образом.
Ясно, что при такой стратегии второго игрока первый не выиграет.
