MathDB

Consider a binary matrix

M

(all entries are

0

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

r R(i)\ge c C(j)

. (Proposed by Gerhard Woeginger, Austria)

Problem Statement