Школьный 10 - 11 класс

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

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

Рассмотрим любую пару соседних клеток разных цветов - если в таблице вообще есть клетки разных цветов, то такая найдётся. Остальные соседи этих клеток совпадают с ними по цвету, поэтому разделяющая цвета граница будет продолжаться в обе стороны, и далее, пока не упрётся в края таблицы:

Получаем, что любая граница между разными цветами должна идти от края до края таблицы, причём с каждой стороны от неё будет одноцветная полоса клеток. Но это означает, что вертикальная и горизонтальная границы одновременно существовать не могут. Следовательно, либо все границы горизонтальные, либо все границы вертикальные, и раскраска в любом случае «полосатая». (Ширина каждой полосы при этом должна быть не менее 2 клеток - впрочем, для решения это значения не имеет.)

Это означает, что либо количества клеток каждого цвета делятся на высоту таблицы, либо на её ширину, как и разность . С другой стороны, эта разность не может быть равна 0 , так как в этом случае и общее количество клеток равно , но на 3 число не делится. Значит, или .

Равенство возможно, если красные клетки занимают 12 столбцов (по 28 клеток), розовые столько же, а синие - 11 столбцов. Если столбцы одного цвета расположить подряд, то все условия задачи будут выполнены.