7
$\begingroup$

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 ?

$\endgroup$

4 Answers 4

19
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ I can't understand this solution. Your solution uses very difficult terminology. Can you please explain in simpler language ? Also, this book is for school students. $\endgroup$ Commented Nov 2, 2023 at 21:03
  • $\begingroup$ Basically, replace all the numbers with "odd" or "even," and then treat the columns like a linear system—there is a way to solve the system such that all the sums are even—it's a fancy way of writing and proving this. $\endgroup$
    – Someone
    Commented Nov 2, 2023 at 21:07
  • $\begingroup$ @HemantAgarwal Sorry to hear that! This solution heavily uses ideas from linear algebra; I'm not sure there's a good way to rewrite the entire proof without using that. Hopefully, someone else will come up with something more elementary. $\endgroup$
    – Ankoganit
    Commented Nov 2, 2023 at 23:12
  • 3
    $\begingroup$ +1 for the first solution, which is natural and clear. $\endgroup$ Commented Nov 3, 2023 at 7:46
  • 1
    $\begingroup$ It's been such a long time since I ceased being a proper mathematician that I was genuinely unsure whether characteristic 2 may somehow screw basic linear algebra here. Which makes me welcome the "elementary" solution even more. $\endgroup$
    – loopy walt
    Commented Nov 3, 2023 at 14:37
8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks..good and simple explanation ..2 requests . First request: Can you please explain loopy walt's induction method ? Pls see my comment below his ans to see where I got stuck . Second request: my own method of solving using induction was proving that if it is true for n*(n+1) then it is also true for n*(n+2) which I was able to do easily. And then i needed to prove that if it is true for n*(n+2) then it will also be true for (n+1)*(n+2) which I was not able to prove. Can you pls help me proving that if it is true for n*(n+2) then it will also be true for (n+1)*(n+2) ? $\endgroup$ Commented Nov 6, 2023 at 15:51
  • $\begingroup$ I think the best way to summarise @loopywalt's answer is "in this case, induction is not the simplest tool for proving the statement" :-) Anyway, I think what it says is "remove a column and row from the grid. By induction hypothesis, the remainder of the numbers will have a solution. If that solution works for the removed row does too, then you're done. If not, pick a different row and try again. If that doesn't work even after trying all the rows, apply Ankoganit's first solution". But I am by no means certain if that's what it actually says :-) $\endgroup$
    – Bass
    Commented Nov 6, 2023 at 17:02
  • $\begingroup$ Also, I don't see any simple way to go from n*(n+2) to (n+1)(n+2). As you clearly have figured out yourself, adding a column is trivial (the same solution still applies), while adding a row very much is not. $\endgroup$
    – Bass
    Commented Nov 6, 2023 at 17:08
  • 1
    $\begingroup$ This is a fantastic explanation! I really like that you have specifically emphasized the main insights where the ocean-crossing happens: it makes the reasoning a lot easier to follow than my write-up. $\endgroup$
    – Ankoganit
    Commented Nov 6, 2023 at 22:16
4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ If the sum of the numbers in each row is even then we don't need to delete any column. $\endgroup$ Commented Nov 2, 2023 at 19:36
  • 3
    $\begingroup$ Anyway, I edited the question to remove the ambiguity. $\endgroup$ Commented Nov 2, 2023 at 19:49
  • $\begingroup$ [ +1 ] Nice Catch , @Horst Walther , with Nicer Example ! $\endgroup$
    – Prem
    Commented Nov 3, 2023 at 5:48
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ So, this is what I understood from your answer. Replace all the even numbers of the table with a 0 and replace all the odd numbers of the table with a 1. Now, prove that that the hypothesis is true for a 1*2 table. Now, assume that the hypothesis is true for an (n-1)*n table. We need to prove that it will also be true for an n*(n+1) table. To do this, take an n*(n+1) table and remove any 1 row r from this table. Now, remove any 1 column from this table. $\endgroup$ Commented Nov 4, 2023 at 3:46
  • 1
    $\begingroup$ We now get an (n-1)*n table and we already know that the hypothesis is true for an (n-1)*n table. We remove some of the columns of the (n-1)*n table to make the sum of each of the rows equal to 0. Now, we insert back the row that we had removed. If the sum of the digits of this row is 0 then we are done. I couldn't understand anything after this especially how to solve it if the sum of the digits of the reinserted row is not equal to 0. Please explain in simpler language what you wish to say. $\endgroup$ Commented Nov 4, 2023 at 3:46
  • $\begingroup$ agree, we were doing ok until "to finish" which should be a paragraph of its own and should actually explain not merely state in words not all readers will know. For example, I know some linear algebra and still do not see "we needn't know any linear algebra to see we can form any vector". This is not math.se. $\endgroup$ Commented Nov 5, 2023 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.