Question

4. Дана белая доска размером 100 x 100 клеток. Двое по очереди красят ее клетки в черный цвет, причем первый всегда закрашивает квадрат 2 x 2, а второй три клетки, образующие «уголок». Уже покрашенную клетку второй раз красить нельзя. Проигрывает тот, кто не может сделать очередной ход. Кто выиграет при правильной игре: первый или второй? Ответ обоснуйте

Answer 1

Ответ: второй. В одном из углов доски второй играющий своим первым ходом закрашивает три клетки в прямоугольнике 2 x 3, а три оставшиеся клетки из этого прямоугольника объявляет «заповедником». В дальнейшем второй делает любые возможные ходы, не затрагивающие клетки «заповедника». Если такой ход становится невозможным, то он закрашивает клетки заповедника. Легко понять, что ответного хода у первого играющего нет.

Answer 2

Для решения данной задачи рассмотрим несколько начальных состояний доски и определим стратегии игроков.

1. Начальное состояние доски:

Copy code
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W

Здесь "W" обозначает белую клетку, которая еще не была закрашена. В этом случае первый игрок, закрашивая квадрат 2 x 2, имеет только один возможный ход. После его хода доска примет следующий вид:

cssCopy code
B B W W W W W W W W
B B W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W

Теперь второй игрок может закрасить любую клетку, кроме клеток, которые уже были закрашены. Пусть он закрасит клетку в правом верхнем углу:

cssCopy code
B B W W W W W W W W
B B W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
B W W W W W W W W W

Теперь первый игрок не может закрасить квадрат 2 x 2, так как верхняя правая клетка уже закрашена. Таким образом, первый игрок проигрывает.

2. Начальное состояние доски:

Copy code
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W

В этом случае первый игрок, закрашивая квадрат 2 x 2, имеет несколько