I got stuck to this problem....

Each of the numbers $a_1,.......,a_n$ is 1 or –1, and we have

$S = a_1a_2a_3a_4+a_2a_3a_4a_5+... +a_na_1a_2a_3 = 0$

Prove that $4|n$.

This is what my book says......

This is a number theoretic problem, but it can also be solved by invariance principle.If we replace any $a_i$ by –$a_i$, then $S$ does not change mod $4$ since four cyclically adjacent terms change their sign. Indeed, if two of these terms are positive and two negative, nothing changes. If one of three have same sign, $S$ changes by$±4$. Finally, if all four are of same sign, then $S$ changes $±8$. Initially, we have $S=0$ which implies $S\equiv 0\pmod 4$. Now, step by step, we change each negative sign into a positive sign. This does not change $S$ mod $4$. At the end, we still have $S\equiv 0\pmod 4$, but also $S=n$, i.e., $4|n$.


An explanation to the OP's answer

Each $a_i$ appears in exactly $4$ terms in the sum. Call these four terms $t_{i1},t_{i2},t_{i3},t_{i4}$ and define $S_i=S-\displaystyle\sum_{j=1}^4 t_{ij}$. If we change $a_i$ to $-a_i$ keeping the rest $a_j$ unchanged, all $t_{ij},1\le j\le4$ will also change sign while $S_i$ remains unaffected as it doesn't contain $a_i$. We will have a new sum, $S'$, given by$$S'=S_i-\sum_{j=1}^4t_{ij}=S-2\sum_{j=1}^4t_{ij}$$Now all you need to show is that $2\mid\displaystyle\sum_{j=1}^4t_{ij}$. This is true, as we can either have all $t_{ij}$'s equal to $\pm1\left(\displaystyle\sum_{j=1}^4t_{ij}=\pm4\right)$, or three of them $\pm1$ and the fourth $\mp1\left(\displaystyle\sum_{j=1}^4t_{ij}=\pm2\right)$, or two $\pm1$ and the other two $\mp1\left(\displaystyle\sum_{j=1}^4t_{ij}=0\right)$. This means $S'\equiv S\mod4$.

Now, if we progressively change all negative $a_i$ to $-a_i$, ultimately each term of the sum will become $1$, and the final sum $S'=\underbrace{1+1\cdot\cdot\cdot+1}_{\text{n times}}=n\equiv S=0\mod 4$. Thus, $n\equiv0\mod4$.


Your Answer

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