edited by
359 views
1 votes
1 votes
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$.
edited by

1 Answer

0 votes
0 votes
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.

Related questions

1 votes
1 votes
0 answers
1
go_editor asked May 30, 2016
341 views
Let $x=(x_1, x_2, \dots x_n) \in \{0,1\}^n$ By $H(x)$ we mean the number of 1's in $(x_1, x_2, \dots x_n)$. Prove that $H(x) = \frac{1}{2} (n-\Sigma^n_{i=1} (-1)^{x_i})$....
3 votes
3 votes
2 answers
4