1/-1 matrix - problem #29 from Problem solving strategies

Here is the solution to one of the problems mentioned in the earlier blog post:

Problem 29: Suppose contrary to the claim a1 + b1 + … + a25 + b25 = 0. Then:

(a1 + a2 + … + a25) = - (b1 + … + b25) ⋯ ①

Now note that ai= -1,if number of elements having value -1 in row i is even, and 1 otherwise.

Thus (a1 + a2 + … + a25) = -x + y,  where x is the number of rows having odd number of -1s and y is the number of rows having even number of -1s ⋯ ②

Similarly, (b1 + … + b25) = -m + n, where m is the number of columns having odd number of -1s and n is the number of columns having even number of -1s ⋯ ③

Combining ①, ② and ③ results in the equation (y – x ) = (m - n) ⋯ ④

But (y + x) = 25, the total number of rows in the matrix, and (m + n) = 25, the total number of columns in the matrix. Thus (y + x) = (m + n) ⋯ ⑤

Combining ④ and ⑤ results in the equality y = m, which implies that the number of rows with even number of -1s equals the number of columns with odd number of -1s.

Define z = number of -1s in the matrix.

Suppose y is odd. Then, x must be even and by original definition of x and y, z must be even (even number of rows with odd number of -1s plus odd number of rows with even number of -1s, resulting in even + even). If y is even, z must be odd. Thus parity(z) ≠ parity(y) ⋯⑥

On the other hand, by definition of m and n, it can be shown that if m is odd, then z must be odd and if m is even then z must be even. Thus parity(z) = parity(m). But this contradicts ⑥ since y = m as per an earlier equation. Thus the assumption a1 + b1 + … + a25 + b25 = 0 is wrong.