М638. Бесконечный лист клетчатой бумаги

Условие

Некоторые клетки бесконечного листа клетчатой бумаги выкрашены в красный цвет, остальные-в синий, причем так, что каждый прямоугольник из $6$ клеток размером $2\times3$ содержит в точности две красные клетки. Сколько красных клеток может содержать прямоугольник из $99$ клеток размером $9\times11$?

Решение

Рассмотрим произвольную красную клетку $K_0$ и рассмотрим квадрат $3\times3$ с центром в этой клетке. Соседние с $K_0$ по горизонтали или вертикали клетки не могут быть красными: если, например, как на рисунке 1,   красной оказалась клетка $K$, то в правом  и левом прямоугольниках  $2\times3$   больше  красных  клеток  не будет,  поэтому  в нижнем  таком  прямоугольнике   окажется  всего  одна  красная  клетка  $K_0$ — противоречие  с условием.  Итак, соседние  с $K_0$  клетки-синие.

Далее,  в правом прямоугольнике должна быть еще одна красная клетка-пусть, например, это будет клетка $K_1$ как на рисунке 2.

Рассматривая верхний и левый прямоугольники $2\times3$ из условия выводим, что в углу нашего квадрата $3\times3$, противоположном клетке $K_1$ тоже должна стоять красная клетка- $K$, и красные клетки в этом квадрате расположены по диагонали. Рассматривая такие же квадраты с центрами в клетках $K_1$ и $K$ и сдвигая эти квадраты далее по «красной диагонали», из приведенного рассуждения получаем, что весь диагональный ряд $KK_0K_1$ состоит из красных клеток, а по два диагональных ряда выше и ниже красного-из синих клеток,  как  показано  на  рисунке  3.

Рассуждая аналогично ( см. рис. 3) ,получаем, что два следующих (сверху и снизу) ряда-красные, затем два ряда-синие, потом опять идут красные ряды, и так далее, как показано на рисунке 4.

Легко видеть, что раскраска рисунка 4 удовлетворяет  условию задачи. При этом каждый квадрат $3\times3$ содержит в точности три красные клетки, а так как прямоугольник $9\times11$ можно разбить на 9 квадратов $3\times3$ и 3 прямоугольника $2\times3$, заключаем, что в этом прямоугольнике $9\cdot3+3\cdot2=33$ красные клетки.

В приведенном рассуждении доказано больше, чем требовалось условием задачи-фактически нами описаны все возможные раскраски.

Отметим, что в этой задаче совсем не обязательно рассматривать раскраску всей плоскости-можно было ограничиться раскраской 99 клеток прямоугольника $9\times11$.