Processing math: 100%

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


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

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

  1
3 года 8 месяца назад #

В русском варианте написано m+n1, но должно быть 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.