6
$\begingroup$

We are given an $n \times n$ board, where $n$ is an odd number. In each cell of the board either $+1$ or $-1$ is written. Let $a_k$ and $b_k$ denote the products of the numbers in the $k$-th row and the $k$-th column, respectively. Prove that the sum $a_1+a_2+\cdots+a_n+b_1+b_2+\cdots+b_n$ cannot equal to $0$

I started off with some examples:


If its a $3 \times 3$ board, then:

you can either have:

  1. five $-1$'s and four $1$'s
  2. five $1$'s and four $-1$'s
  3. three $1$'s and six $-1$'s
  4. three $-1$'s and six $1$'s
  5. two $-1$'s and seven $1$'s
  6. two $1$'s and seven $-1$'s
  7. one $1$'s and eight $-1$'s
  8. one $-1$'s and eight $1$'s

regardless, the sum will never be $0$.

but how would i prove that?

$\endgroup$
  • 1
    $\begingroup$ Look at the 8 sums you calculated for a 3 by 3 board. What do all of these sums have in common? $\endgroup$ – Joey Zou Nov 21 '15 at 5:23
  • $\begingroup$ Actually, I'm not so sure that just specifying how many 1's and -1's is enough to determine the sum $a_1+a_2+...+a_n+b_1+...+b_n$. Work out a few examples of the sums you get by filling in a 3 by 3 in different ways. What do you notice about the sums? $\endgroup$ – Joey Zou Nov 21 '15 at 5:30
3
$\begingroup$

The product of the $a_i$ is equal to the product of the $b_i$. This is because each of these products is the product of all the elements in the $n\times n$ array.

So the numbers of $-1$'s among the $a_i$, and among the $b_i$, have the same parity (both numbers are even or both are odd).

It follows that the combined number of $-1$'s among the $a_i$ and $b_i$ is even.

This ensures that the sum of all the $a_i$ and all the $b_i$ cannot be $0$. For if the sum is $0$, the total number of $-1$'s among the $a_i$ and $b_i$ must be $n$. And $n$ is odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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