Problem from Olympiad from book Arthur Engel

Question

Each of the numbers $a_1 ,a_2,\dots,a_n$ is $1$ or $−1$, and we have $$S=a_1a_2a_3a_4+a_2a_3a_4a_5 +\dots+ a_na_1a_2a_3=0$$ Prove that $4 \mid n$.

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 or three have the same sign, $S$ changes by $\pm 4$. Finally, if all four are of the same sign, then $S$ changes by $\pm $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$. This is the solution . Can somebody explain the last part ,where we change sign and how in the end $S=n$.

Made any progress on this problem? It would be helpful to add to the question an outline of what you have tried or ideas you have had so the question does not get closed due to lack of context. — Peter Woolfitt, Jun 11 '15 at 06:45
Also, do you possibly mean Arthur Engel instead of Arthur Angel? — Peter Woolfitt, Jun 11 '15 at 06:47
This is idea ....If we replace any a (i )by −a( i) , then S does not change mod 4 since four cyclically adjacent terms change their sign.....This is the basic idea . From here we have to proceed.@peter Woolfitt — Bluey, Jun 11 '15 at 06:53
Well, the post has changed while I wrote my answer... The last part means the sum of $a_i$s is $n$ if all $a_i$ are changed to +1. — cjackal, Jun 11 '15 at 07:02
See also Prove that n is divisible by 4 in a cylic sum with variables which have only two possible values — Bart Michels, Aug 11 '15 at 10:22

score 11 · Accepted Answer · answered Jun 11 '15 at 06:58

11

Think of the case that all of $a_i$ are 1. Then obviously $S=n$.

Then change the sign of $a_i$ one by one and examine the change of $S$.

Because each $a_i$ affects 4 terms in $S$, which are from $a_{i-3}a_{i-2}a_{i-1}a_i$ to $a_i a_{i+1}a_{i+2}a_{i+3}$ so sum to even, and the sum of these 4 terms are changed to became the negative of original sum, we know that each change of sign of $a_i$ changes the value of $S$ by a multiple of 4.

So, $n$, the original $S$, experiences sequences of addition with multiples of 4 to become 0, which means $n \equiv 0 $ mod 4.

answered Jun 11 '15 at 06:58

cjackal

2,173

Thanks :)...........It was right before my eyes :) – Bluey Jun 11 '15 at 07:03
Perfect answer +1 – Cloud JR K Jul 08 '18 at 06:27

Problem from Olympiad from book Arthur Engel

1 Answers1

Linked