Pinko wrote: We will call a rectangular table filled with natural numbers “good”, if for each two rows, there exist a column for which its two cells that are also in these two rows, contain numbers of different parity. Prove that for $\forall$ $n>2$ we can erase a column from a good $n$ x $n$ table so that the remaining $n$ x $(n-1)$ table is also good. Joint solution(with varying contributions ) with MathPassionForever, biomathematics and Yagami1728: Replace every number in the tables with their parities(id est, every odd number is replaced with $1$ and every number is replaced with $2$, as we only care about the parity of the entry and not the numbers themselves.) Immediately note that the problem implies that no two rows can be identical. Two rows are said to differ at column $X$ if they differ in their entries in only one column, which is column $X$. We call a column of a good $n$ x $n$ table deletable, if it can be deleted without making the resulting $n$ x $(n-1)$ table bad. Say for a given good $n$ x $n$ table, there are no deletable columns. Then, for every column $x$, we must have at least one pair of cells in it such that the rows that these cells belong differ at the column $x$. Consider a graph $G$ with $n$ vertices $r_1,r_2, \dots r_n$, so that each vertex represents a row of the table. Now for each column $x$, join some two vertices if the rows that these vertices represent differ at column $x$. So, we have a graph $G$ with $n$ vertices and at least $n$ edges. This means that it must contain a cycle of length $\ge 3$. Let the cycle be $s_1-s_2- \dots -s_k-s_1$( where $s_i$ are the vertices that belong to this cycle). Now, let the row that $s_i$ represent be $R_i$ and the column where $s_i$ and $s_{i+1}$(where $s_{k+1}$ is taken as $s_1$) differ be called $C_i$. Then in the table, we get that $R_i$ and $R_{i+1}$ differ at $C_{i}$ for all $ 1 \le i \le k$. Now, see that as, $R_1$ and $R_2$ differ at $C_1$, $R_2$ and $R_3$ differ at $C_2$ and as $R_1$ and $R_2$ are identical at $C_2$ and as $R_2$ and $R_3$ are identical at $C_1$,we get that $R_1$ and $R_3$ have different entries at both $C_1$ and $C_2$. Continuing in a similar fashion, we get that $R_1$ and $R_k$ must be different at at least $k-1$ columns($k>2$). But as $s_k$ and $s_1$ are adjacent in $G$ , it means that $R_1$ and $R_k$ differ at $C_k$; id est, they have different values at only 1 column(which is $C_k$). Contradiction! Hence, we must have atleast one deletable column in a good $n$ x $n$ table.

Is there a linear algebra approach to this problem?