Color a 1000 by 1000 grid with 0s and 1s

Question

Show that one could remove 990 rows with a 1 remaining in every column, OR delete 990 columns with 0 in remaining in every row. My approach: let $r_i$ be the number of 1s in row i and $c_i$ be the number of 0s in column i but then I am stuck. Any hint would be appreciated!

Answer 1

Not a solution, too long for comments. I was thinking on the problem and decided to write my thoughts; my first idea was to use the pideonhole principle and it would be straightforward; it is more complicated than I thought.

A second idea is to try to use some linear indepedence argument, considering rows and columns as vectors on $\mathbb{Z}_2^{1000}$. This sounds familiar, but I could not find a way to express the conditions on this new angle.

Any comments/suggestions are welcome.

---

Pidgeonhole attempt. Let us fix some notation. Denote $[n] = \{1, 2, \ldots, n\}$ and also for some set $X$ let $$ \binom{X}{n} = \{Y \subset X; |Y| = n\} $$ the family of all subsets of $X$ with precisely $n$ elements. Using your notation for $r_i$ and $c_i$, we have $$ \sum_1^{1000} c_i + \sum_1^{1000} r_i = 1000 \cdot 1000 = 10^6, $$ since we are counting each $1$ and each $0$ exactly once. For some $X \in \binom{[1000]}{10}$, let us denote $$ r_X = \sum_{i \in X} r_i. $$ Using the pidgeonhole principle, if you have a grid that is $10 \times 1000$ that has at least $999 \cdot 10 + 1$ elements being $1$, then you found a selection of rows that satisfies the first statement. Otherwise, for every $X \in \binom{[1000]}{10}$ you have $$ r_X \le 9990. $$ Now, we make a counting in two ways argument. Notice that $$ \sum_{X \in \binom{[1000]}{10}} r_X = \binom{999}{9} \cdot \sum_{1}^{1000} r_i, $$ since every row belongs to precisely $\binom{999}{9}$ sets of $10$ rows (just choose $9$ other rows from the remaining $999$). The computations above show that if we do not have the first statement then $$ \sum_{1}^{1000} r_i \le \frac{\binom{1000}{10}}{\binom{999}{9}} \cdot 9990 = \frac{1000!}{999!} \cdot \frac{9! \cdot 990!}{10! \cdot 990!} \cdot 9990 = 1000 \cdot 999 $$ and thus the average row has at most $999$ ones.

Symmetric argument for $c_i$. Analogously, if we have some $1000 \times 10$ grid with at least $999 \cdot 10 + 1$ entries being zero then every row must have a zero. The same double counting argument proves that $$ \sum_1^{1000} c_i \le 1000 \cdot 999. $$

Answer 2

Suppose it is impossible to delete 990 rows so that there is a 1 in every column. This means, any 10 rows always have a column with only 0s. For rows $10i ... 10i + 9$, denote the all-zero column by $z_i$, for $i = 0...9$. This gives 10 columns.

If we now delete all but these 10 columns $z_i$, we guaranteed a 0 in every row. (So column $z_0$ will have 0 in the first 10 rows, column $z_1$ will have a 0 in the next 10 rows, and so on.)

---

This is a variation on the following observation:

In any rectangle colored with 0s and 1s, we have both the following being true:

• either a 1 in every column, or a 0 in every row.
• either a 1 in every row, or a 0 in every column.

(To see that this is true, take the first statement as an example. If we do NOT have a one in every column, there is a column with all 0s, and so we are guaranteed a 0 in every row.)