Республиканская олимпиада по математике, 2012 год, 9 класс

Клетки доски $(2m+1)\times (2n+1)$ красятся в два цвета — белый и черный. Единичная клетка строки (столбца) называется доминирующей по строке (по столбцу), если более половины клеток этой строки (этого столбца) имеет одинаковый цвет с этой клеткой. Докажите, что по крайней мере $m+n-1$ клеток доски одновременно доминируют по строке и по столбцу.

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

В русском варианте написано $m+n-1,$ но должно быть $m+n+1.$

Решение: Пусть $A$ $-$ количество клеток доски которые одновременно доминируют по строке и по столбцу,

$B$ $-$ количество клеток доски которые доминируют только по строке,

$C$ $-$ количество клеток доски которые доминируют только по столбцу.

Заметим, что $A+B+C\le (2m+1)(2n+1).$

Из того, что $(A+B)$ $-$ это количество клеток которые доминируют хотя бы по строке, то $A+B\ge (n+1)(2m+1),$ поскольку в каждой строке (их $2m+1$) хотя бы $(n+1)$ клеток доминируют по ней. Аналогично $A+C\ge(m+1)(2n+1).$ Тогда получаем, что

$$(n+1)(2m+1)+(m+1)(2n+1)\le (A+B)+(A+C)=A+(A+B+C)\le A+(2m+1)(2n+1)$$

$$\implies A\ge (n+1)(2m+1)+(m+1)(2n+1)-(2m+1)(2n+1)=m+n+1.\quad\blacksquare$$