Suppose $n$ is odd and each square of an $n \times n$ grid is arbitrarily filled with either by $1$ or by $-1$. Let $r_j$ and $c_k$ denote the product of all numbers in $j$-th row and $k$-th column respectively, $1 \le j, k \le n$. Prove that $$\sum_{j=1}^{n} r_j+ \sum_{k=1}^{n} c_k\ne 0$$
Problem
Source: CRMO 2014 region 2 p6
Tags: combinatorics, number theory, grid
30.09.2018 08:41
Assume that $\sum_{j=1}^{n} r_j+ \sum_{k=1}^{n} c_k = 0$. $\Longrightarrow$ the number of $(-1)$ in $r_j$ and $c_k$ is $n$. Assume that the number of the $(-1)$ in $c_k$ is $m$,then the number of $(-1)$ in $r_j$ is $n-m$. The product of all the numbers in the squares is : $$\prod_{k=1}^{n} c_k= \prod_{j=1}^{n} r_j $$$$(-1)^m=(-1)^{n-m}$$We have two cases: Case.1: : $m$ is even number then since $n$ is odd we will have $1=-1$ contradiction. Case.2: : $m$ is odd number then since $n$ is odd we will have $-1=1$ contradiction. So we are done... $\blacksquare$
30.09.2018 16:15
Each step we replace any $-1$ remaining in the square by a $1$. Then in each step, suppose that we replace the -1 in the $j$-row and $i$-column, we change the sign of $r_{j}$ and $c_{i}$. Hence, the mod $4$ of the sum is unchanged. After the last step, we have a square full of 1s, since n is odd, the final sum does not divides $4$. Therefore, the initial sum cannot divides $4$, so it cannot be $0$.