Цена игры

Мы уже решали эту задачу симметричной стратегией для Пети, то есть оценку на мы уже получили (так как по этой стратегии у Пети больше столбцов, чем у Васи, и строк). Приведем стратегию для Васи, которая обеспечивает .

Будем играть за Васю и стараться ходить симметрично Пете относительно центральной клетки. То есть после каждого хода Пети ставим нолик в симметричную клетку, если она свободна. Если симметричная клетка занята, то ставим в любую другую свободную.

Таким образом в любой момент времени после хода Васи будет верен следующий инвариант: для каждого Петиного крестика (кроме центрального) будет пара — симметричный ему нолик, и еще может быть будут нолики без пары. Инвариант всегда выполняется, так как он выполняется в самом начале игры (до первых ходов) и, если он выполнялся на данном шаге, то будет выполняться и на следующем (благодаря нашей стратегии).

Следовательно, и в конце игры доска будет симметричной относительно центральной клетки (в любых двух симметричных клетках будет нолик и крестик). То есть число строк, в которых больше ноликов, будет не больше чем на 1 меньше числа строк, в которых больше крестиков (так как только центральная строка не имеет своей противоположной симметричной пары). Аналогично со столбцами.

Значит, по такой стратегии .