Using Pigeon Hole principle

combinatoricspigeonhole-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?

Best Answer

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.