Весенний тур. Тренировочный вариант. 8-9 класс (5)

Ответ: при n > 4 и n = 4.

Докажем, что первый игрок сможет выиграть при любых n, больших 4.

Будем называть дырой ломаную из нескольких неокрашенных сторон, идущих подряд. После первого хода n - 1 неокрашенных сторон образуют дыру. Заметим, что по условию второй игрок не сможет уменьшить количество дыр. Иначе, он бы покрасил сторону, которая граничит с двумя покрашенными. А по правилам, он этого сделать не может.

Стратегия первого игрока: каждым ходом создавать новую дыру длиной 1, пока это возможно. (Заметим, что при n > 4 первый игрок уже на втором своем ходу обязательно создаст хотя бы одну дыру длины 1, то есть такие дыры обязательно будут.) Если он не может создать новую дыру длины 1, то неокрашенными остались несколько дыр длиной 1 и, быть может, дыра длины 2. Если такая дыра есть, то первый красит одну из маленьких дыр. Второму приходится покрасить сторону большой дыры, и после очередного хода первого игрока он проигрывает. Если же дыры длины 2 нет, то первый может покрасить любую дыру и второй снова проиграет.

Остается рассмотреть случаи n = 3 и n = 4.
При n = 3, очевидно, выигрывает первый игрок.
А при n = 4 при любой игре выигрывает второй.