Клетки не более чем двух цветов в каждой строке или столбце

[Ktina]

Можно ли раскрасить клетки доски $9\times 9$ в 3 цвета так, чтобы выполнялись два условия: а) клеток всех цветов поровну б) в каждой строке или столбце были клетки не более чем двух цветов?
(Всероссийская олимпиада школьников. Омская область)

Довольно долго ничего не приходило на ум, а все попытки доказательства невозможности построения требуемой в задаче конструкции претерпевали крах.

Спустя некоторое время родилась вот такая странная конструкция:

А А А А А А В В В
А А А Б Б Б Б Б Б
В В В Б Б Б В В В
А А А А А А В В В
А А А Б Б Б Б Б Б
В В В Б Б Б В В В
А А А А А А В В В
А А А Б Б Б Б Б Б
В В В Б Б Б В В В

Стало быть, ответ на задачу, всё-таки, "да"?
Хотелось бы понять, какие там глубинные закономерности.
Пожалуйста, помогите решить.
Заранее спасибо!

[svv]

Ktina в сообщении #1140550 писал(а):

Хотелось бы понять, какие там глубинные закономерности.

Если условия выполняются, перестановка строк или столбцов их не нарушит. Поэтому можно использовать перестановки, чтобы придать конструкции более простой вид. И наоборот, более сложный вид считать «испорченным» перестановками.

Квадрат $9\times 9$ («большой») можно разбить на $9$ квадратов $3\times 3$ («средних»). Попробуйте перестановками добиться того, чтобы в пределах каждого «среднего» квадрата все «маленькие» квадратики были одного цвета.

[Ktina]

svv в сообщении #1140552 писал(а):

Квадрат $9\times 9$ («большой») можно разбить на $9$ квадратов $3\times 3$ («средних»). Попробуйте перестановками добиться того, чтобы в пределах каждого «среднего» квадрата все «маленькие» квадратики были одного цвета.

А А А А А А В В В
А А А А А А В В В
А А А А А А В В В
А А А Б Б Б Б Б Б
А А А Б Б Б Б Б Б
А А А Б Б Б Б Б Б
В В В Б Б Б В В В
В В В Б Б Б В В В
В В В Б Б Б В В В

Вы это имели в виду?

[svv]

Да. Так как цвета маленьких в одном среднем одинаковые, можно условиться изображать только цвета средних.
Отразим картинку, чтобы уголки из одинаковых букв, как стрелочки, указывали вправо-вверх (самое оптимистичное направление):
В А А
Б Б А
В Б В
Если идея ещё не видна, сейчас будет. Заполним этим паттерном плоскость:

Во-первых, обратите внимание, что даже в бесконечных столбцах и строках лишь по два цвета в каждом.
Во-вторых, строить из этого решение исходной задачи можно, как минимум, двумя способами: можно как угодно выделить здесь квадрат $3\times 3$ и каждый его квадратик разбить на $9$ маленьких. А можно как угодно выделить здесь квадрат $9\times 9$ и ничего больше не делать.

[Ktina]

svv
Большое спасибо!