Республиканская олимпиада по математике, 2012 год, 9 класс
Клетки доски (2m+1)×(2n+1) красятся в два цвета — белый и черный. Единичная клетка строки (столбца) называется доминирующей по строке (по столбцу), если более половины клеток этой строки (этого столбца) имеет одинаковый цвет с этой клеткой. Докажите, что по крайней мере m+n−1 клеток доски одновременно доминируют по строке и по столбцу.
посмотреть в олимпиаде
Комментарий/решение:
В русском варианте написано m+n−1, но должно быть m+n+1.
Решение: Пусть A − количество клеток доски которые одновременно доминируют по строке и по столбцу,
B − количество клеток доски которые доминируют только по строке,
C − количество клеток доски которые доминируют только по столбцу.
Заметим, что A+B+C≤(2m+1)(2n+1).
Из того, что (A+B) − это количество клеток которые доминируют хотя бы по строке, то A+B≥(n+1)(2m+1), поскольку в каждой строке (их 2m+1) хотя бы (n+1) клеток доминируют по ней. Аналогично A+C≥(m+1)(2n+1). Тогда получаем, что
(n+1)(2m+1)+(m+1)(2n+1)≤(A+B)+(A+C)=A+(A+B+C)≤A+(2m+1)(2n+1)
⟹A≥(n+1)(2m+1)+(m+1)(2n+1)−(2m+1)(2n+1)=m+n+1.◼
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.