Дана квадратная таблица n x n (n > 3), все клетки которого изначально белые. Разрешается поменять цвет клетки (с белого на черный и с черного на белый) в фигуре в форме буквы «Т» (см. рисунок), которая может быть повернута на 90, 180 или 270 градусов. Докажите, что если и не делится ни на 2, ни на 3, то таблицу нельзя перекрасить так, чтобы все клетки стали черными.

Дано n × n таблица (n > 3), все клетки изначально белые. Разрешается перекрашивать клетки в фигуре в форме буквы «Т» (можно поворачивать на 90, 180, 270 градусов). Нужно показать: если n не делится ни на 2, ни на 3, то перекрашивать так, чтобы все клетки стали черными, невозможно. Пояснение и решение (пошагово): 1) Как устроена операция - В каждой операции мы перекрашиваем цвет ровно в 4 клетках (потому что Т-форма состоит из 4 клеток: одна центральная и три плеча). - Перекрашивание одной клетки меняет число черных клеток на ±1; поэтому перекрашивание 4 клеток меняет число черных клеток на сумму четырёх таких изменений. 2) Как сохраняется четность числа черных клеток - Рассмотрим B — количество черных клеток на доске после некоторого количества ходов. - При перекрашивании 4 клеток каждый из этих 4 изменений меняет B на ±1. Сумма четырёх таких изменений даёт изменение B по модулю 2 равное 0, потому что 4 — чётное. - Следовательно, B по модулю 2 не меняется после любой операции. То есть B остаётся чётным на всём протяжении игры. 3) Что происходит в начале и в конце - Изначально все клетки белые, значит B = 0 (чётно). - Если бы мы смогли сделать все клетки чёрными, то B бы стал равным n^2. - По условию задачи n не делится на 2, значит n — нечётное, поэтому n^2 тоже нечётно, то есть нечетно. 4) Противоречие - Соревнование требует, чтобы B после последней операции был чётным (из п. 2), но если все клетки черные, B = n^2 — нечётно. - Противоречие. Значит добиться всех клеток черными невозможно. 5) Что означает условие задачи - Мы доказали более сильное утверждение: для всех нечётных n (а значит и для любых n, не делящихся на 2) перекрашивание всех клеток не может быть достигнуто, независимо от того, делится ли n на 3 или нет. - В формулировке же условия говорят «если не делится ни на 2, ни на 3», что именно охватывает нечётные n; наш аргумент по чётности уже достаточно. Дополнительная заметка - Если бы фигура Т имела не 4, а другое число клеток (например, 5 клеток, как в некоторых вариантах задач с пятиугольной буквой «Т»), простого чётного инварианта по числу черных клеток может оказаться недостаточно. В таком случае часто применяют модульные цветовые инварианты (например, окрашивание по трём цветам и использование сумм по модулю 3). Но для данного варианта, где «Т» состоит из 4 клеток, достаточно рассуждения по чётности числа черных клеток, как выше. Итог - При n, не делящемся ни на 2, ни на 3 (то есть при нечётном n), перекрасить всю доску в чёрный цвет невозможно, потому что число чёрных клеток остаётся чётным после любой операции, а наконец получается нечётное число черных клеток, что невозможно.