Q3 Matemática  (Mediterranean Mathematics Olympiad 2012)

Considere uma matriz binária $M$(todas as entradas são $0$ ou $1$) em $r$ linhas e $c$ colunas, onde cada linha e cada coluna contém pelo menos uma entrada igual a $1$. Prove que existe uma entrada $M(i,j)=1$, tal que a soma da linha $R(i)$ e a soma da coluna $C(j)$ satisfaçam $rR(i)\ge cC(j)$. (Proposto por Gerhard Woeginger, Áustria)