by showmyiq » Sun May 05, 2013 7:49 am
The puzzle is cracked by Sergey Sokolov via Facebook. I am going to publish his solution here:
We have:
\begin{equation}
a_1 a_2 + a_2 a_3 + ... + a_{n-1} a_n + a_n a_1 = 0 \\
\end{equation}
Let’s define set A, such that:
\begin{equation}
A=[a_1,a_2,a_3,a_4,...,a_n]
\end{equation}
Let’s define the function F, such as:
\begin{equation}
F(A)=a_1 a_2 + a_2 a_3 + ... + a_{n-1} a_n + a_n a_1 \\
\end{equation}
Now what if we reflect only one of the elements in set A? By reflecting Sergey defined if the element is -1, the reflected one will be 1. If the element is 1, the reflected element will be -1. If the element is equal to x, the reflected element will be –x. So let’s take one aj, for some j that 0<j<(n+1) and let’s reflect it.
\begin{equation}
A=[a_1,a_2,a_3,a_4,...,aj,..,a_n]\\
A_{reflected} = B =[a_1,a_2,a_3,a_4,...,-aj,..,a_n]\\
\text{let's calculate F(A) and F(B)}\\
F(A)=a_1 a_2 + a_2 a_3 + ... + a_{j-1}a_j + a_ja_{j+1}...+ a_{n-1} a_n + a_n a_1 \\
F(B)=a_1 a_2 + a_2 a_3 + ... + a_{j-1}(-a_j) + (-a_j)a_{j+1}...+ a_{n-1} a_n + a_n a_1 \\
F(B)=a_1 a_2 + a_2 a_3 + ... - a_{j-1}a_j - a_ja_{j+1}...+ a_{n-1} a_n + a_n a_1 \\
\text{now let's see what will be the difference between F(B) and F(A)}\\
F(B)-F(A) = a_1 a_2 + a_2 a_3 + ... - \color{red}{a_{j-1}a_j} - \color{red}{a_ja_{j+1}}...+ a_{n-1} a_n + a_n a_1 - \\ (a_1 a_2 + a_2 a_3 + ... + \color{red}{a_{j-1}a_j} + \color{red}{a_ja_{j+1}}...+ a_{n-1} a_n + a_n a_1) \\
F(B)-F(A) = a_1 a_2 + a_2 a_3 + ... - \color{red}{a_{j-1}a_j} - \color{red}{a_ja_{j+1}}...+ a_{n-1} a_n + a_n a_1 - \\a_1 a_2 - a_2 a_3 - ... - \color{red}{a_{j-1}a_j} - \color{red}{a_ja_{j+1}}...- a_{n-1} a_n - a_n a_1 \\
F(B)-F(A) = -2*\color{red}{a_{j-1}a_j} -2*\color{red}{a_ja_{j+1}}
\end{equation}
The multiplication of two random elements can be either 1 or -1. So we can see that F(B)-F(A) can be equal to -4, 0, or 4 (all dividable by 4).
Now let’s take a set C, that poses only 1’s:
\begin{equation}
C=[\underbrace{1,1,...,1}_n]\\
F(C)=\underbrace{1*1 + 1*1 + ... + 1*1 + 1*1}_n \\
F(C)=n*1 = n
\end{equation}
Since F(A) is F(C) with some elements mirrored/reflected/flipped - we can reach A from C, using the same transformation from A to B we did in the beginning, and this transformation should be applied several times ( in fact the count of the times is equal to the count of the elements in the set that should be reflected).
\begin{equation}
\text{let's define one reflection step as }\zeta_i \\
Then:\\
F(A) = F(C) + \zeta_1 + \zeta_2 + .. + \zeta_\mu \\
\text{all of the zeta functions are equal to either -4, either 0 or either 4} \\
\text{let's m,n and p is the count of those equal to -4,0 and 4} \\
F(A) = F(C) + \zeta_1 + \zeta_2 + .. + \zeta_\mu \\
F(A) = F(C) + m*(-4) + n*0 + p*4 \\
F(A) = F(C) -4m + 4p \\
\text{but F(C) is equal to n, and F(A) is equal to 0}\\
0 = n - 4m + 4p \\
n = 4m - 4p\\
n = 4(m-p)
\end{equation}
Therefore n is dividable by 4.