1

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!

Kai
  • 874
  • 4
  • 14
  • What are rules to color the grid? e.g. what if you color all cells with 0? one of your statements immediately becomes false – caverac Sep 18 '19 at 17:52
  • Counterexample: imagine a checkerboard pattern of $1$s and $0$s. My guess is that you need to be a little bit more specific about what you want. – Andrew Chin Sep 18 '19 at 17:52
  • What do you mean by "10 rows with a 1 in every column in those rows"? What is a column in a row? – 79037662 Sep 18 '19 at 17:53
  • Standard checkerboard pattern fails this. Seems like there are conditions missing. – Thomas Andrews Sep 18 '19 at 18:09
  • If I color all cells with 0, then I can find 10 columns such that a 0 appear in every row – Kai Sep 18 '19 at 18:45
  • Only one of the conditions need to be true – Kai Sep 18 '19 at 18:46
  • Standard chess board pattern pass both conditions. Take two adjacent rows/ columns. – Kai Sep 18 '19 at 18:48
  • @Kai No row or column is all black or all white on a standard chess board. – David P Sep 18 '19 at 18:50
  • If you remove the first 990 rows from a checkerboard pattern then doesn't that still leave 5 1's in each column? – Daniel Schepler Sep 18 '19 at 18:56
  • @DavidPeterson, I can find 10 COLUMNS (and thus remove 990 COLUMNS) such that a 0 appear in every ROW in the checkboard pattern, because two adjacent columns can cover every row with 0s. – Kai Sep 18 '19 at 19:02
  • @Kai You changed the question substantially. Your CAPSLOCK is not eloquent. – David P Sep 18 '19 at 19:23

2 Answers2

3

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.)

Herman Tulleken
  • 3,608
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. $$

D. Ungaretti
  • 2,668
  • Great idea, but it seems like you are running around in circles and don't really have arrived at a contradiction because from my understanding, you've only proved $1000^2<1000*1998$ – Kai Sep 20 '19 at 05:47
  • Yeah, I know... but maybe this motivates someone to get started on the problem... I think there must be some solution along these lines, but making a more careful use of pidgeonhole principle. The problem is that the condition for ensuring e.g. on every row a $1$ is too strong... It needs a lot of ones. Don't know how to ask for less for the moment. – D. Ungaretti Sep 20 '19 at 17:55
  • 1
    And actually, we could say something a little bit stronger but still useless; since $\sum c_i + \sum r_i = 10^6$, one of the sums must be $\le 500 \cdot 1000$. So I proved that $1000^2 < 1000 \cdot (500 + 999)$. :) – D. Ungaretti Sep 20 '19 at 18:00