The important thing thought is to

cut back the numbers modulo 2, after which deal with the columns as vectors in $mathbb F_2^{n}$. Name these vectors $c_1,dots, c_{n+1}$. Right here $mathbb F_2$ is the sector of integers modulo 2.

Then, since there are $n+1$ columns,

these column vectors should be linearly dependent: there exists $a_1,dots, a_{n+1}in {0,1}$, not all zero, in order that $a_1c_1+cdots+a_{n+1}c_{n+1}$ is the zero vector (modulo 2).

Then we’re finished by

crossing out the columns for which $a_i=0$.

Edit: This is one other extra elementary answer that is trickier to consider (in my view), however accessible to high-school college students.

Notice that every one that issues is the parity of the numbers, we simply must hold observe of strange/even-ness of the row-sums fairly than the precise values. Now,

there are $n$ rows, so there are $2^n$ potentialities for the the parity of the row sums. Nevertheless, there are $2^{n+1}-1$ methods to delete some (however not all) columns, which is definitely greater than $2^n$.

This implies

there are a minimum of two alternative ways to delete the columns that yield the identical sample of parities for the row sums.

Now the trick is that

when you pick the columns which can be left undeleted in precisely one among these two methods, and delete the remaining columns, that will get us finished!

Why? Nicely, let’s clarify this with an instance.

Suppose within the first selection of columns, the columns $1,3,5,6$ get left undeleted, and within the second case, the columns $1,4,5,7,8$ keep undeleted. The belief says including the columns $1+3+5+6$ offers the identical sample of odds and evens within the row sums, as including the columns $1+4+5+7+8$.

However meaning,

if I add all of them collectively, ending up with 2 copies of column 1, two copies of column 5, and one copy every of columns $3,4,6,7,8$, we get even sums in every row! Nevertheless, the columns that get added twice do not contribute to the parity in any respect, so including columns $3,4,6,7$ and $8$ would give even sums in every row as nicely.