Question

Женя и Саша играют в игру «крестики-крестики». Игра заключается в том, что Женя и Саша по очереди ставят крестики на доску 36×36, при этом нельзя ставить 9 крестиков подряд по вертикали или по горизонтали (по диагонали можно). Какое наибольшее количество крестиков Женя и Саша могут поставить на доску?

Answer 1

Пошаговое объяснение:

Если разделить поле 36*36 на квадраты 8*8 то получиться 16 квадратов. В каждом квадрате 64 клетки. И посередине каждых четырёх квадратов ставим крестик, получается ещё 16 крестиков. Итак, вычисляем:

1) 64*16=1024 (крестика)

2) 1024+16=1040 (крестиков)

Ответ:

Женя и Саша могут поставить 1040 крестиков

(У них руки не отвалятся?)

Можно пожалуйста отметить как лучший? Я старалась :3

Answer 2

Предположим, что Женя начинает игру, и они будут ставить крестики поочередно. Чтобы максимизировать количество крестиков на доске, нужно использовать оптимальную стратегию.

Поскольку они не могут ставить 9 крестиков подряд ни по вертикали, ни по горизонтали, оптимальный вариант - это распределение крестиков в шахматном порядке: начать с крестика в углу доски, затем в соседней клетке по диагонали, затем через одну клетку по вертикали и так далее.

Примерное распределение первых нескольких ходов может выглядеть следующим образом (где X - крестик, _ - пустая клетка):

pythonCopy code
X _ _ X _ _ X _ _ X _ _ ...
_ X _ _ X _ _ X _ _ X _ ...
X _ _ X _ _ X _ _ X _ _ ...
_ X _ _ X _ _ X _ _ X _ ...
X _ _ X _ _ X _ _ X _ _ ...
_ X _ _ X _ _ X _ _ X _ ...
...

В этом распределении на каждой диагонали появляется 6 крестиков перед тем, как они начнут повторяться. Таким образом, на доске 36x36 можно разместить максимум 6 крестиков на каждой диагонали.

Доска имеет 36 диагоналей (18 диагоналей сверху вниз и 18 диагоналей снизу вверх), поэтому максимальное количество крестиков будет:

Максимальное количество крестиков = 6 (крестиков на диагональ) * 36 (диагоналей) = 216.

Итак, наибольшее количество крестиков, которое Женя и Саша могут поставить на доску 36x36, равно 216.