Задача 5. Кресты, кратные трём

Считаем красные клетки в кресте

Назовём крестом фигуру из одной строки и одного столбца; клетку, где они пересекаются, назовём центром креста. В кресте $100 + 100 - 1 = 199$ клеток: центр входит и в строку, и в столбец.

Посчитаем в кресте красные клетки. Сложим красные клетки строки и красные клетки столбца. Если центр белый, мы ничего не посчитали дважды. Если центр красный, он попал в обе суммы, и его надо один раз вычесть:

Дальше удобно писать коротко: центр «равен» $1$, если он красный, и $0$, если белый. Тогда в кресте ровно (красных в строке) + (красных в столбце) − центр. По условию это число делится на $3$ для каждой клетки таблицы, взятой центром.

Главное наблюдение: сравниваем две строки

Условие касается сразу $10\,000$ крестов, и в лоб с ним не справиться. Поищем кресты, которые почти совпадают: тогда их разность будет простой.

Возьмём любые две строки $A$ и $B$ и какой-нибудь столбец. Сравним два креста: «строка $A$ + этот столбец» и «строка $B$ + тот же столбец». Столбец у них общий, и при вычитании он сокращается (рисунок ниже):

Назовём поправкой число $\text{центр}_A - \text{центр}_B$: это клетка строки $A$ в этом столбце минус клетка строки $B$ в том же столбце. Поправка равна $0$ (клетки одного цвета), $1$ (в $A$ красная, в $B$ белая) или $-1$ (наоборот).

Оба креста делятся на $3$, значит, и их разность делится на $3$. Поэтому поправка в этом столбце даёт при делении на $3$ тот же остаток, что и число (красных в $A$ − красных в $B$). Это число одно и то же для всех столбцов! Значит, во всех столбцах поправки дают одинаковый остаток при делении на $3$.

Но $-1$, $0$ и $1$ дают разные остатки: любые два из них отличаются на $1$ или на $2$, а это не делится на $3$. Значит, поправка во всех столбцах одна и та же. Возможны три случая:

• поправка везде $0$: в каждом столбце клетки строк $A$ и $B$ одного цвета, то есть строки $A$ и $B$ совпадают;
• поправка везде $1$: в каждом столбце клетка строки $A$ красная, а строки $B$ белая, то есть строка $A$ целиком красная, а строка $B$ целиком белая;
• поправка везде $-1$: наоборот, $A$ целиком белая, $B$ целиком красная.

Итог: любые две строки либо совпадают, либо одна из них целиком красная, а другая целиком белая. В модели это видно в разделе «Сравни две строки».

Какой может быть вся таблица

Разберём два случая.

Все строки одинаковые. Тогда если клетка в каком-то столбце красная в одной строке, она красная и во всех строках. Значит, красные клетки составляют несколько целых столбцов, а остальные столбцы целиком белые.

Есть две разные строки. По шагу 2 одна из них — назовём её $К$ — целиком красная, а другая целиком белая. Возьмём любую третью строку $X$ и сравним её с $К$. Если $X$ совпадает с $К$, она целиком красная. Если не совпадает, то по шагу 2 одна из строк $X$, $К$ целиком красная, а другая целиком белая; красная — это $К$, значит, $X$ целиком белая. Итак, каждая строка целиком красная или целиком белая: красные клетки составляют несколько целых строк.

Строки и столбцы в условии равноправны: если повернуть таблицу на четверть оборота, строки станут столбцами, а каждый крест останется крестом. Поэтому достаточно разобрать раскраску целыми столбцами — для строк всё будет так же.

Сколько столбцов может быть красными

Пусть красные клетки — это $s$ целых столбцов. Так как $N > 0$, есть хотя бы один красный столбец: $s \ge 1$. В каждой строке ровно $s$ красных клеток — по одной в каждом красном столбце. Посчитаем по шагу 1 два вида крестов (рисунок ниже).

• Центр в белом столбце: в строке $s$ красных, в столбце $0$, центр белый. В кресте $s$ красных клеток.
• Центр в красном столбце: в строке $s$, в столбце все $100$ клеток, центр красный. В кресте $s + 100 - 1 = s + 99$ красных клеток.

Может ли вся таблица быть красной ($s = 100$)? Тогда белых столбцов нет, и в каждом кресте $100 + 99 = 199$ красных клеток. Но $199 = 3 \cdot 66 + 1$ на $3$ не делится. Значит, $s < 100$ и белый столбец есть. Крест с центром в белом столбце даёт: $s$ делится на $3$. Тогда и $s + 99$ делится на $3$, ведь $99 = 3\cdot 33$.

Итак, $s$ — одно из чисел $3, 6, 9, \ldots, 99$, то есть $s = 3k$, где $k = 1, 2, \ldots, 33$. Красных клеток $N = 100\cdot s = 300k$. Для раскраски целыми строками получаются те же числа.

Каждое такое N действительно бывает

Осталось показать, что каждое из чисел $300, 600, \ldots, 9900$ получается. Возьмём $k$ от $1$ до $33$ и покрасим целиком любые $3k$ столбцов, например первые. Тогда $N = 100 \cdot 3k = 300k$.

Проверим все кресты по шагу 4 при $s = 3k$:

• центр в белом столбце: в кресте $3k$ красных клеток — делится на $3$;
• центр в красном столбце: в кресте $3k + 99 = 3(k + 33)$ красных клеток — тоже делится на $3$.

Других крестов нет: центр всегда стоит в белом или в красном столбце. Значит, все $33$ значения подходят, а других, по шагам 2–4, нет.