# Using Pigeon Hole principle

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?

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.

• 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? – cgss Sep 30 '20 at 12:15
• Thanks for that. But please consider answering question asked by @cgss. – nmnsharma007 Sep 30 '20 at 12:32
• Also what if you don't have a row with at least two zeroes anymore? – nmnsharma007 Sep 30 '20 at 13:14
• @cgss You are right, there is a mix of two things here. I updated my proof. – WhatsUp Sep 30 '20 at 13:38

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.

• Thanks.Understood – nmnsharma007 Sep 30 '20 at 13:58