ISI2014-PCB-A-2a

Question

Let $A$ be a $30 \times 40$ matrix having $500$ non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column.

Show that there is a k such that $1 \leq k \leq 30$, $r_k \geq 17$ and there is an $l$ such that $1 \leq l \leq 40$, $m_l \leq 12$.

Answer 1

Total no of non-zero entries=500

Total rows=30

Now, (500/30)>16.

So there will be at least one row for which no of non-zero entries will be >=17.

 

Total columns=40

Now, (500/40)<13.

So there will be at least one column for which no of non-zero entries will be <=12.