Математикадан республикалық олимпиада, 2011-2012 оқу жылы, 9 сынып

Өлшемі $\left( {2m + 1} \right) \times \left( {2n + 1} \right)$ болатын тақтаның әрбір бірлік шаршысы екі түске — ақ және қара — боялған. Егер жолдағы (бағандағы) бірлік шаршылардың саны сол жолдың (бағанның) бірлік шаршысымен бір түстес болса, онда осы бірлік шаршыны жол (баған) бойынша басым дейміз. Ең кем дегенде тақтаның $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$$