Expert: Scott A Wilson - 10/15/2009

Question
Let n ≥ 2 be an integer and let x1, x2, ......., xn ∈ {−1, 1} such
that
x1x2 + x2x3 + ....... + xn−1xn + xnx1 = 0
Prove that n is divisible by 4.

Answer
If xi is an element of {-1,1}, then let n be 2.
The results are

x1 x2  x1•x2 + x3•x1
1 -1  -1 + -1 = -2
1  1   1 +  1 =  2
-1 -1   1 +  1 =  2, and
-1  1 has the same results as 1 -1.

For n = 3, the results are
x1 x2 x3   x1•x2 + x2•x3 + x3•x1
-1 -1 -1   1+1+1 =  3
-1 -1  1   1-1-1 = -1
-1  1 -1  -1-1+1 = -1
-1  1  1  -1+1-1 = -1
1 -1 -1  -1+1-1 = -1
1 -1  1  -1-1+1 = -1
1  1 -1   1-1-1 = -1
1  1  1   1+1+1 =  3
This is seen to not be true as well, since none of the sums are 0.

For four elements, 1 1 1 -1 turns into 1+1-1-1 = 0, so it can be seen to hold here.

For each string of -1's in the set, that leaves a -1 at either end.
To cancel this, there must be 2 +1's as well, for a total of four elements.
There must be at least one -1, which means there are two.
FOr every two -1's, there must be 2+1's.
2 -1's and 2+1's leads to a string of elements where n is divisible by 4.

See, every -1 in the string generates two -1's.
If there is a string of -1's in the string, it generates one at either end.
Two cancel these two -1's takes two +1's, and that is a total of four elements.

In this way, n has to be divisible by 4.