Each cell of a 1997x1997 square grid contains either +1 or -1, with no cell being vacant.

The product of all the numbers in the ith row, and the product of all the numbers in the ith column are respectively denoted by R_i and C_i.

               1997
Prove that  Σ_i=1(R_i + C_i) is always nonzero.

(In reply to re: a simple proof by Daniel)

You are right,Daniel.

Still, the same proof is applicable to the product case.

I have erased one figure and  now I paste  the new text, just solving two problems for the price of one....And here we go:

Imagine all squares having +1 as a content. The overall sum-the one called sigma- will equal 2*1997  which is  2 mod 4. <br> Changing square a(i,j) to -1 will  reduce the sum in row i by 2 , and in column j by 2 , leaving the overall sum  still equal to  2 mod 4.<br><br>

 if we continue and make further changes (1 into -1) striving to reduce the overall sum and get 0,- one of the following will happen:<br>

a) both the row's  and column's sums will decrease by 2.<br>

b) both the row's  and column's sums will increase by 2.<br>

c) one sum will increase and the other decrease by 2.<br>

In all those cases the overall sum will remain 2 mod 4 and 0 mod 4 cannot be reached.<br><br>

Since any  matrix out of (1997*1997)! existing can be constructed by the process I described - no matrix with sigma=0 exists.    q.e.d.

 

 

Posted by Ady TZIDON on 2010-04-29 17:25:25