2-я Международная Жаутыковская олимпиада, 2006 год

Прямоугольную таблицу $m\times n$ ($4\leq m\leq n$) назовем хорошей , если в каждую ее клетку можно вписать число 0 или 1 так, чтобы одновременно выполнялись условия:
1) не все вписанные числа равны 0 и не все равны 1;
2) число единиц во всех квадратах $3\times 3$ одно и то же;
3) число единиц во всех квадратах $4\times 4$ одно и то же.
Найдите все пары натуральных чисел $(m, n)$ ($4\leq m\leq n$), для которых существует хорошая таблица $m\times n$.

Комментарий/решение

Пример для $m=4$:

1111111...

000000...

000000...

1111111...

Пример для $m=5$:

1111111...

1111111...

000000...

1111111...

1111111...

Примера для $6$ x $6$ нет, поэтому подходят только $m=4$ и $m=5$

От противного, посчитаем сумму чисел, когда будем проходиться по каждому квадратику $3x3$ и $4x4$. Несложно убедиться, что эти суммы совпадают, но они делятся на $9$ и $16$, значит сумма делится на $9*16$, но сумма максимум $9*16$, но тогда все числа должны быть равны $1$, противоречие