2
$\begingroup$

There is a $2n\times 2n$ matrix consisting of $0$ and $1$ and there are exactly $3n$ zeroes. Show that it is possible to remove all zeroes by removing some $n$ rows and $n$ columns.

Now I am able to see intuitively how this is true. But how to prove this using Pigeon Hole Principle?

$\endgroup$
5
$\begingroup$

We show that

if there are $n + k$ rows with at most $n + 2k$ zeros, then we may remove $k$ rows such that there are at most $n$ zeros in the remaining $n$ rows.

We prove by induction on $k$. For $k = 0$ there is nothing to prove.

Now suppose we have $n + k$ rows and at most $n + 2k$ zeros. Without loss of generality, we may assume that there are exactly $n + 2k$ zeros (otherwise, we pretend that some of the ones were zeros, and proceed as follows).

Since there are $n + 2k$ zeros and only $n + k$ rows, pigeon hole principle tells us that there exists one row that contains at least $2$ zeros. We remove that row.

Now there remains $n + (k - 1)$ rows and at most $n + 2(k - 1)$ zeros, so the induction hypothesis finishes the rest.


For $k = n$, we have shown that if there are $3n$ zeros in $2n$ rows, then we may remove $n$ rows such that there remains at most $n$ zeros.

Then simply remove all the columns containing at least a zero.

$\endgroup$
4
  • 4
    $\begingroup$ That was my thought exactly but then I notice that if we remove exactly one row and one column we are left with a $2n - 1 \times 2n - 1$ matrix but for the induction to work we should have $2(n-1) \times 2(n-1)$. Am I missing something? $\endgroup$ – cgss Sep 30 '20 at 12:15
  • 1
    $\begingroup$ Thanks for that. But please consider answering question asked by @cgss. $\endgroup$ – nmnsharma007 Sep 30 '20 at 12:32
  • 1
    $\begingroup$ Also what if you don't have a row with at least two zeroes anymore? $\endgroup$ – nmnsharma007 Sep 30 '20 at 13:14
  • 2
    $\begingroup$ @cgss You are right, there is a mix of two things here. I updated my proof. $\endgroup$ – WhatsUp Sep 30 '20 at 13:38
3
$\begingroup$

The $n$ "high" rows containing the most zeros must contain at least $2n$ zeros (doesn't matter how we allocate marginal rows with an equal count so long as the total for the high rows is maximised).

If not, there are at least $n+1$ zeros to fit in the other $n$ "low" rows, and one of the low rows must contain at least two (pigeonhole). Also there are at most $2n-1$ zeros to fit in the high rows and one of these rows must contain just one. But this contradicts the definition of the high rows.

Hence we can choose $n$ rows to eliminate at least $2n$ zeros, and we need at most $n$ columns to eliminate the remaining (at most $n$) zeros.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks.Understood $\endgroup$ – nmnsharma007 Sep 30 '20 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.