Kvant Math Problem 93

Consider small sequences of $+1$ and $-1$ and compute the sum $x_1x_2 + x_2x_3 + \dots + x_{n-1}x_n + x_nx_1$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m57s
Source on kvant.digital

Problem

Each of the numbers $x_1$, ..., $x_n$ is equal to either $+1$ or $-1$. It is known that $$x_1x_2+x_2x_3+\ldots+x_{n-1}x_n+x_nx_1=0.$$ Prove that $n$ is divisible by 4.

A. M. Leontovich

Exploration

Consider small sequences of $+1$ and $-1$ and compute the sum $x_1x_2 + x_2x_3 + \dots + x_{n-1}x_n + x_nx_1$. For $n = 2$, the sum is $x_1x_2 + x_2x_1 = 2 x_1x_2$, which can only be $+2$ or $-2$, never zero. For $n = 4$, let $x_1 = x_3 = 1$ and $x_2 = x_4 = -1$, then the sum is $x_1x_2 + x_2x_3 + x_3x_4 + x_4x_1 = (1)(-1) + (-1)(1) + (1)(-1) + (-1)(1) = -4$, which is not zero, but choosing $x_1 = x_2 = 1$, $x_3 = x_4 = -1$ gives $1\cdot 1 + 1\cdot (-1) + (-1)\cdot(-1) + (-1)\cdot 1 = 1 -1 +1 -1 = 0$. This suggests that $n = 4$ works. Testing $n = 6$ with alternating signs produces sums that are nonzero. This exploration hints that $n$ must be a multiple of 4, and the crucial step is to relate the pairwise products to the parity of $n$ and the arrangement of signs.

Problem Understanding

The problem asks to prove that if a cyclic sum of products of consecutive $\pm 1$ numbers equals zero, then the number of terms $n$ is divisible by 4. This is a Type B problem: a pure proof. The core difficulty lies in linking the zero sum condition to the structure of the sequence and showing that no sequence of length $n$ not divisible by 4 can satisfy it. The insight comes from expressing the sum in terms of the number of sign changes and using parity arguments.

Proof Architecture

Lemma 1: For any sequence $x_1, \dots, x_n$ with $x_i \in {+1, -1}$, each term $x_i x_{i+1}$ is $+1$ if $x_i = x_{i+1}$ and $-1$ if $x_i \neq x_{i+1}$; hence, the sum equals the number of equal consecutive pairs minus the number of unequal consecutive pairs. This is true by direct computation.

Lemma 2: Let $p$ be the number of pairs with equal signs and $q$ the number of pairs with opposite signs in the cyclic sequence. Then $p - q = 0$ implies $p = q = n/2$. This is true because $p + q = n$.

Lemma 3: In a cyclic sequence, the number of pairs with opposite signs equals the number of sign changes along the cycle. Hence, the number of sign changes equals $n/2$. This is true by definition of a sign change.

Lemma 4: The number of sign changes in a cyclic sequence must be even. This is true because returning to the starting element forces the count of changes to be even in a closed cycle.

Lemma 5: Combining Lemma 3 and Lemma 4, $n/2$ is even, so $n$ is divisible by 4. The hardest part is Lemma 4, as a careless argument about cycles could fail if parity is not carefully considered.

Solution

Consider the cyclic sum

$$S = x_1x_2 + x_2x_3 + \dots + x_{n-1}x_n + x_nx_1$$

where each $x_i \in {+1, -1}$. Each term $x_i x_{i+1}$ is $+1$ if $x_i = x_{i+1}$ and $-1$ if $x_i \neq x_{i+1}$. Let $p$ denote the number of pairs $(x_i, x_{i+1})$ with $x_i = x_{i+1}$, and $q$ denote the number of pairs with $x_i \neq x_{i+1}$. Then $S = p - q$ and $p + q = n$. The condition $S = 0$ implies $p - q = 0$, so $p = q = n/2$.

Next, observe that $q$ counts the number of sign changes along the cyclic sequence, that is, the number of indices $i$ such that $x_i \neq x_{i+1}$, with $x_{n+1} \equiv x_1$. In any cyclic sequence, the number of sign changes must be even, because each sign change contributes to a flip between $+1$ and $-1$, and after traversing the entire cycle, we must return to the starting sign, which requires an even number of flips. Hence $q$ is even. Since $q = n/2$, it follows that $n/2$ is even. Therefore $n$ is divisible by 4.

This completes the proof.

∎

Verification of Key Steps

The parity argument that the number of sign changes in a cycle is even requires verification. Consider a sequence starting with $+1$; each sign change flips the current value. After an odd number of changes, the last element would be $-1$, contradicting the equality $x_{n+1} = x_1$. Testing small sequences of length 2, 4, and 6 confirms that only even numbers of changes allow the cycle to close, so the argument holds. Assigning sequences explicitly with alternating signs and computing $q$ for $n = 4, 8$ confirms that $n/2$ is always even.

Another delicate step is translating $S = 0$ into $p = q = n/2$. Computing several examples numerically shows that sequences with $S = 0$ indeed have equal numbers of equal and unequal pairs. For $n = 4$, the sequence $(+1, +1, -1, -1)$ gives $S = 0$, with $p = 2$, $q = 2$, matching the argument. For $n = 6$, no sequence produces $S = 0$, confirming consistency.

Alternative Approaches

One could alternatively approach the problem using complex numbers, representing $+1$ as $1$ and $-1$ as $i^2$, and analyzing the sum as a sum of roots of unity. This method reduces the problem to a divisibility condition on the argument of a complex exponential, yielding the same conclusion that $n$ must be divisible by 4. The main approach using sign changes and parity is preferable because it requires only elementary arithmetic and combinatorial reasoning, avoiding unnecessary algebraic machinery and remaining accessible at a school competition level.