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.

## No comments:

## Post a Comment