Using Pigeon Hole principle

Question

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?

Answer 1

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.

Answer 2

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.