Consider a binary matrix M(all entries are 0 or 1) on r rows and c columns, where every row and every column contain at least one entry equal to 1. Prove that there exists an entry M(i,j)=1, such that the corresponding row-sum R(i) and column-sum C(j) satisfy rR(i)≥cC(j).
(Proposed by Gerhard Woeginger, Austria) inequalitieslinear algebramatrixinductioncombinatorics unsolvedcombinatorics