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.

<meta http-equiv="Content-Type" content="text/html; charset=utf-8"><meta name="ProgId" content="Word.Document"><meta name="Generator" content="Microsoft Word 11"><meta name="Originator" content="Microsoft Word 11"><link rel="File-List" href="file:///C:%5CUsers%5CConall%5CAppData%5CLocal%5CTemp%5Cmsohtml1%5C01%5Cclip_filelist.xml"><style> </style>

I think this should do it. Consider any grid with X rows and Y columns where all cells contain the value 1.  Σ_i=1(R_i + C_i) = X + Y.

<o:p> </o:p>

From here we have two possible moves:

<o:p> </o:p>

(i)              If we change the sign of cell (X_i , Y_i ) where R_i and C_i have opposite signs, the total will remain unchanged, as we are only swapping the positions of the +1 and -1.

<o:p> </o:p>

(ii)            If we change the sign of cell (X_i , Y_i ) where R_i and C_i have the same sign, the total will either increase by 4 (if we go from two -1s to two +1s) or decrease by 4.

<o:p> </o:p>

Thus, we can only ever change the total in even amounts of 4.

<o:p> </o:p>

In the case of a 1997 x 1997 grid.

Σ_i=1(R_i + C_i)     = 1997 + 1997

                        = 1997 * 2

= A number which clearly does not have 4 as a factor, so we cannot lower the total to 0.

Posted by farcear on 2010-04-29 12:18:11