It is quite hard to explain, but I will try. The question is equivalent to showing we can choose 10 rows so at least a '1' in each column, or 10 columns with a '0' in every row. (in fact 9 is enough) First we let $R$ be the 1000x1000 table. (*) Now if there are more 0 than 1, then there will be a column with more 0 than 1, or the same. We can switch the necessary rows and colums such that that column will be at the left of $R$, and all the 1 are above the 0 in that column. Now we redefine $R$ to be a rectangle in the original $R$, whose rows are the rows in $R$ whose first cell is 1, and we exclude the first column. See picture. (I'm sorry, the spaces did not turn out right) _______ |1| | | | R | |_|_____| |0| | | | | |_|_____| If there are more 1 than 0, then repeat the same as above, except replace the rows with column and columns with rows. Picture. ____________ |__0__|__1__| | R | | |_____|_____| We repeat everything again at (*) until $R$ do not exist, i.e. $R$ will have a 0 length or height. Suppose it is 0 length, then we take the first 9 rows from the top. There will be at least $500+250+125+63+32+16+8+4+2=1000$ 1's, all from different columns. Similarly for the 0 height case. So we are done.

The idea is to generalize and induct. Suppose that we have a grid with at most $2^m$ rows and $2^n$ columns. We prove that either we can leave at most $m$ columns, such that each row has at least one $1$, or at most $n$ rows, such that each column has at least one zero. We induct on $m+n$. The base case is clear. Suppose WLOG that there are more zeroes than ones in the grid. Hence, there is a row $R$ with more zeroes than ones. There are at most $2^{n-1}$ columns intersecting $R$ at a $1$, so delete the other columns and now the I.H. holds (and let now the previously mentioned row be $R'$). In this new grid, if we can leave at most $m$ columns, such that each row has at least one $1$, then adding the previously deleted columns doesn't create any problem and thus this choice works for the original grid. So, suppose we can leave at most $n-1$ rows in the new table, such that each column has at least one zero. The row $R'$ has only ones in the new grid, so it is not among the chosen $n-1$, since it has no effect on the columns. Now, take those at most $n-1$ rows in the original grid and add to them $R$; notice that this choice works as every deleted column has a zero in $R$.