Prove that in an n*(n+1) table filled with integers, we can always cross out some columns and make the sum of the integers in each row, even

Question

The boxes of an n * (n+1) table ( n rows and n+1 columns) are filled with integers. Prove that one can cross out zero or several columns ( not all of them ) so that after this operation, the sum of the numbers in each row is even.

From the book, Mathematical circles Russian experience.

P.S: Also, can someone help me complete my partial attempt at solving this using induction.

This is my attempt using induction: I first proved for the 1 * 2 table. Then successfully proved that whenever it is true for the n * (n+1) case, it would also be true for the n * (n+2) case. Now, I needed to prove that whenever it is true for the n * (n+2) case, it would also be true for the (n+1) * (n+2) case. But, this is where I failed. Can someone please help me with the proof for the last part ?

Answer 1

The key idea is to

reduce the numbers modulo 2, and then treat the columns as vectors in $\mathbb F_2^{n}$. Call these vectors $c_1,\dots, c_{n+1}$. Here $\mathbb F_2$ is the field of integers modulo 2.

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

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

Then we are done by

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

Edit: Here's another more elementary solution that's trickier to think of (in my opinion), but accessible to high-school students.

Note that all that matters is the parity of the numbers, we just have to keep track of odd/even-ness of the row-sums rather than the actual values. Now,

there are $n$ rows, so there are $2^n$ possibilities for the the parity of the row sums. However, there are $2^{n+1}-1$ ways to delete some (but not all) columns, which is certainly bigger than $2^n$.

This means

there are at least two different ways to delete the columns that yield the same pattern of parities for the row sums.

Now the trick is that

if you pick out the columns that are left undeleted in exactly one of these two ways, and delete the remaining columns, that gets us done!

Why? Well, let's explain this with an example.

Suppose in the first choice of columns, the columns $1,3,5,6$ get left undeleted, and in the second case, the columns $1,4,5,7,8$ stay undeleted. The assumption says adding the columns $1+3+5+6$ gives the same pattern of odds and evens in the row sums, as adding the columns $1+4+5+7+8$.

But that means,

if I add all of them together, ending up with 2 copies of column 1, two copies of column 5, and one copy each of columns $3,4,6,7,8$, we get even sums in each row! However, the columns that get added twice don't contribute to the parity at all, so adding columns $3,4,6,7$ and $8$ would give even sums in each row as well.

Answer 2

@Ankoganit's brilliant answer gives the proof on two different levels, the easier of which should be accessible with high school mathematics. I liked the proof quite a lot, so I wanted to try and rewrite it so that it can be understood with very little maths at all. Here's what I ended up with.

To reiterate the puzzle setup,

1. we have a rectangular grid of numbers, and
2. we can toggle each column on or off independently. Then
3. for each row, (of which there are fewer than columns), we check if the toggled-on numbers in that row add up to an even or an odd number.

With all that, our task is to prove that in addition to the "all columns off" state, there is always another way to make every row total show "even".

Following the method in @Ankoganit's answer (or at least something that works in an analogous fashion), we can start by toggling all the columns off, and then, one by one, we'll try every possible combination of columns, and write down the exact pattern of odds and evens in the row sums.

For example, if the numbers and row sums look like this with all the columns A to E toggled on

6 9 2 4 7 even
7 1 0 8 2 even
7 1 3 5 2 even
6 1 3 4 5  odd
A B C D E

we'd start systematically writing down what the row sums are when only a portion of the columns is toggled on:

A:     even-odd-odd-even
B:     odd-odd-odd-odd
A+B:   odd-even-even-odd
C:     even-even-odd-odd
A+C:   ...
B+C:   ...
A+B+C: ...
D:     ...

and so on.

Then comes the first clever bit: no matter what the actual numbers in the grid are, we are always guaranteed to find a pair. That is, we can always find two column combinations that will produce the exact same pattern of odds and evens for the row sums. Why? Because of the grid shape, and something called the pigeonhole principle: There are more columns than there are rows, so there are also more column combinations (each column is either on or off) than there are possible distinct patterns of row sums (each row sum is either odd or even). If you try to match each column combination to a different row sum pattern, you will run out of row sum patterns first, so by necessity, some row sum pattern(s) must have more than one column combination that produces them.

So, we know we can always find a pair, which is when the second clever bit of Ankoganit's answer steps in: We can do addition to such a pair! If we toggle one of the combinations first, and then the second one, then each row sum will be either "even+even=even", or "odd+odd=even", and that's exactly what we wanted!

There's a final catch though: what if both the combinations in the pair included the same column? We cannot very well include the same column twice, now can we?

Turns out, this is not a problem at all. We just need to notice that adding a number changes parity in exactly same way that subtracting does, so if we need to toggle on a column that was already on, we can achieve the exact same effect by toggling that column back off.

That covers all the cases, so the proof is complete, and since we never used the grid size or the specific contents of the grid in the proof, it applies to all grids that fit the initial description. Just for fun and illustration purposes, we can then apply it to our example case:

A:       even-odd-odd-even
B:       odd-odd-odd-odd
A+B:     odd-even-even-odd
C:       even-even-odd-odd
A+C:     even-odd-even-odd
B+C:     odd-odd-even-even
A+B+C:   odd-even-odd-even
D:       even-even-odd-even
A+D:     even-odd-even-even
B+D:     odd-odd-even-odd
C+D:     even-even-even-odd
A+B+D:   odd-even-odd-odd
A+C+D:   even-odd-odd-odd
B+C+D:   odd-odd-odd-even
A+B+C+D: odd-even-even-even
A+E:     odd-odd-odd-odd (same as B)

and now that we finally found a pair, we can add A+E to B to achieve the desired "even-even-even-even" at "A+B+E":

6 9 - - 7 even
7 1 - - 2 even
7 1 - - 2 even
6 1 - - 5 even
A B C D E

Finally, to demonstrate the "other kind of addition", we can notice that this was not actually the first pair we found: at the start, we had already calculated A+B+C+D+E=even-even-even-odd, which is the same pattern as C+D, so we could have also done A+B+C+D+E + C+D = A+B+C+D+E-C-D = A+B+E = even-even-even-even to reach the same result.

Hope this was worth your time, and if you find something that could be made even more clear, please do drop a comment; that would be much appreciated.

Answer 3

Maybe I do not understand the question. But in the 2*3 table

• 110
• 011

you cannot cross out any one or two columns and get even sums. On the other hand the original table contains even sums in both rows. "Several" means (for me as a non-English speaker) at least one. so this is a counterexample.

What is probably meant is: Prove that one can cross out 0 or more columns (but not all of them) so that after this operation, the sum of the numbers in each row is even.

Answer 4

At OP's special request here is a proof by induction:

Note: I first tried writing the following without using "modulo 2" but now think it is not worth the clutter.

Thus we rephrase given an n x (n+1) table of numbers mod 2 we can always find a nonempty set of columns that sum to the zero vector.

The assertion is easily confirmed for 1x2 tables, i.e. n=1.

Now assume it has been established for (n-1) x n. Given an n x (n+1) table T pick and remove a column c and set it aside. After also removing any row r we can apply the assumption to find a nonempty set S(c,r) of columns that does not include the c-th such that their sum as column vectors vanishes everywhere except possibly in row r. If the r-th row also vanishes the proof is complete. As this last statement holds for any r, to finish, we need only consider the case where for all r the sum of S(c,r) is $e_r$, the r-th standard basis vector. Having the entire standard basis at our disposal we needn't know any linear algebra to see that we can form any vector, in particular, we can express the c-th column in terms of the other columns. As we are modulo 2 all coefficients are either one or zero, i.e. "yes" or "no". Recall that we have so far avoided using column c. Adding it now yields the zero vector as sum of a set of columns that include column c hence is nonempty.