Некоторые клетки бесконечного листа клетчатой бумаги окрашены в красный цвет, остальные в синий, причём так, что каждый прямоугольник из 6 клеток размером $2\times3$ содержит в точности две красные клетки. Сколько красных клеток может содержать прямоугольник из 99 клеток размером $9\times11$?
Н. Карташов
Всесоюзная математическая олимпиада (XIV, 1980 год, 8 класс)
Ответ. В любом прямоугольнике $9\times11$ содержится 33 красные клетки.
Доказательство. Рассмотрим произвольную красную клетку $K_0$ и рассмотрим квадрат $3\times3$ с центром в этой клетке. Соседние с $K_0$ по горизонтали или вертикали клетки не могут быть красными: если, например, как на рисунке 1, красной оказалась клетка $K$, то в правом и левом прямоугольниках $2\times3$ больше красных клеток не будет, поэтому в нижнем таком прямоугольнике окажется всего одна красная клетка ($K_0$) — противоречие с условием. Итак, соседние c $K_0$ клетки — синие.
Далее, в правом прямоугольнике должна быть ещё одна красная клетка — пусть, например, это будет клетка $K_1$, как на рисунке 2. Рассматривая верхний и левый прямоугольники $2\times3$, из условия задачи выводим, что в углу нашего квадрата $3 \times 3$, противоположном клетке $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$ красные клетки.
В приведённом рассуждении доказано больше, чем требовалось условием задачи — фактически нами описаны все возможные раскраски.
Большинство читателей рассуждали иначе: прямоугольник $9\times11$ легко разбить на 16 прямоугольников $2\times3$, после чего останется полоска $1\times3$. Из условия нетрудно получить, что в этой полоске может содержаться только одна красная клетка, поэтому во всем прямоугольнике — только $16\cdot2+1=33$ красные клетки. После этого достаточно привести пример раскраски, которая удовлетворяет условию задачи.
Отметим, что в этой задаче совсем не обязательно рассматривать раскраску всей плоскости — можно было ограничиться раскраской 99 клеток прямоугольника $9\times11$.
