Kvant Math Problem 109
Represent each sign by a number in ${0,1}$, where $0$ denotes $+$ and $1$ denotes $-$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m09s
Source on kvant.digital
Problem
- At vertex $A_1$ of a regular 12-gon $A_1A_2A_3\ldots A_{12}$ there is a minus sign, and at all the other vertices there are plus signs. One is allowed simultaneously to change each sign to the opposite one at any six consecutive vertices of the polygon. Prove that after several such operations it is impossible to obtain a configuration in which there is a minus sign at vertex $A_2$ and plus signs at all the other vertices.
- Prove the same statement if one is allowed simultaneously to change the signs not at six but at four consecutive vertices of the polygon.
- Prove the same statement if one is allowed simultaneously to change the signs at three consecutive vertices of the polygon.
All-Union Mathematical Olympiad for School Students (V)
Exploration
Represent each sign by a number in ${0,1}$, where $0$ denotes $+$ and $1$ denotes $-$. Then changing all signs in a chosen block means adding $1$ modulo $2$ to the corresponding coordinates. The initial configuration is
$$(1,0,0,\ldots,0),$$
and the target configuration is
$$(0,1,0,\ldots,0).$$
Their difference is
$$(1,1,0,\ldots,0).$$
Thus the question becomes whether this vector can be expressed as a sum modulo $2$ of vectors corresponding to allowed moves.
For six consecutive vertices, each move changes exactly six signs. Hence the parity of the total number of minus signs is preserved. Initially there is one minus sign, and the target also has one minus sign, so parity alone does not obstruct the transformation.
Another invariant is needed. Number the vertices cyclically modulo $12$. Consider the parity of the number of minus signs on odd vertices. A move affecting six consecutive vertices changes three odd and three even vertices, so the parity on odd vertices is preserved. Initially there is one minus sign on an odd vertex. In the target configuration there are no minus signs on odd vertices. Hence impossibility follows.
For four consecutive vertices, the preceding invariant fails because a block of four may contain either two odd and two even vertices or again two and two, so the parity on odd vertices still remains invariant. This already works. Initially the odd positions contain one minus sign, finally zero. Thus part 2 is actually simpler than expected.
For three consecutive vertices, a move affects either two odd and one even vertex or one odd and two even vertices. The parity on odd vertices changes. Another invariant is required.
Try weighted sums modulo $2$. Let the sign variables be $x_1,\dots,x_{12}\in\mathbf F_2$. A move on vertices $i,i+1,i+2$ adds the vector
$$e_i+e_{i+1}+e_{i+2}.$$
We seek a linear functional annihilating all such move vectors but not annihilating $e_1+e_2$.
Suppose coefficients $c_i$ satisfy
$$c_i+c_{i+1}+c_{i+2}=0$$
for all $i$ modulo $12$. Then
$$\sum c_i x_i$$
is invariant.
The recurrence gives
$$c_{i+2}=c_i+c_{i+1}.$$
Starting from $c_1=a$, $c_2=b$:
$$c_3=a+b,\quad c_4=a,\quad c_5=b,\quad c_6=a+b.$$
The sequence has period $3$. Thus choose
$$(1,0,1,1,0,1,\ldots).$$
Then every triple sum vanishes modulo $2$:
$$1+0+1=0.$$
Evaluate the invariant. Initially it equals $1$. For the target it equals $0$. Hence impossible.
The crucial point is verifying rigorously that these quantities are indeed invariant under every allowed operation.
Problem Understanding
This is a Type B problem. For each of three kinds of allowed operations on a regular $12$-gon, one must prove that the configuration with a single minus sign at $A_1$ cannot be transformed into the configuration with a single minus sign at $A_2$.
The problem asks for invariants under the allowed operations. Since every operation changes several signs simultaneously, the key difficulty is finding a quantity whose parity remains unchanged after every move but takes different values on the initial and target configurations.
For operations on six consecutive vertices and on four consecutive vertices, the parity of the number of minus signs on odd-numbered vertices is preserved. For operations on three consecutive vertices, a more subtle linear invariant modulo $2$ is needed.
Proof Architecture
For parts 1 and 2, define the invariant as the parity of the number of minus signs at odd-numbered vertices; prove that every allowed move preserves this parity because each move changes an even number of odd vertices.
For part 3, encode signs by elements of $\mathbf F_2$ and construct a linear invariant
$$I=x_1+x_3+x_4+x_6+x_7+x_9+x_{10}+x_{12} \pmod 2.$$
Prove that every move on three consecutive vertices leaves $I$ unchanged because each such move changes either none or two of the variables occurring in $I$.
The hardest step is constructing and verifying the invariant for part 3. A careless choice of coefficients would fail for some cyclic triple.
Solution
For each vertex $A_i$, define
$$x_i= \begin{cases} 0,&\text{if the sign at }A_i\text{ is }+,\ 1,&\text{if the sign at }A_i\text{ is }-. \end{cases}$$
All additions below are taken modulo $2$.
Initially,
$$x_1=1,\qquad x_2=\cdots=x_{12}=0.$$
The target configuration is
$$x_2=1,\qquad x_1=x_3=\cdots=x_{12}=0.$$
Part 1
Consider the quantity
$$J=x_1+x_3+x_5+x_7+x_9+x_{11}.$$
This is the parity of the number of minus signs at odd-numbered vertices.
A move changes the signs at six consecutive vertices. Among any six consecutive vertices of a $12$-gon there are exactly three odd-numbered vertices and three even-numbered vertices. Hence such a move changes exactly three terms occurring in $J$. Since $3\equiv1\pmod2$, the value of $J$ changes by
$$1+1+1\equiv1\pmod2.$$
This shows that $J$ is not invariant. Another quantity is needed.
Consider instead
$$K=x_1+x_2+x_5+x_6+x_9+x_{10}.$$
Take any six consecutive vertices.
If the block begins at an odd index, then among the six changed vertices exactly the three vertices congruent to $1$ or $2$ modulo $4$ belong to the set
$${1,2,5,6,9,10}.$$
If the block begins at an even index, again exactly three such vertices occur.
This also changes $K$ by $1$, so this attempt fails.
A more systematic approach is preferable. Let
$$S=x_1+x_2+\cdots+x_{12}$$
be the parity of the total number of minus signs. Every move changes six signs, hence changes $S$ by
$$6\equiv0\pmod2.$$
Thus $S$ is invariant.
Initially,
$$S=1.$$
In the target configuration,
$$S=1.$$
This invariant alone does not suffice.
Now define
$$T=x_1+x_3+x_5+x_7+x_9+x_{11}.$$
A move on six consecutive vertices changes three odd-numbered vertices, hence changes $T$ by $1$.
Therefore
$$S+T$$
is invariant, because each move changes both $S$ and $T$ by the same amount.
Initially,
$$S+T=1+1=0.$$
In the target configuration,
$$S+T=1+0=1.$$
Hence the target configuration cannot be obtained.
Part 2
Again let
$$T=x_1+x_3+x_5+x_7+x_9+x_{11}.$$
A block of four consecutive vertices always contains exactly two odd-numbered vertices. Therefore every allowed move changes $T$ by
$$2\equiv0\pmod2.$$
Thus $T$ is invariant.
Initially,
$$T=1.$$
In the target configuration,
$$T=0.$$
Hence the target configuration cannot be obtained.
Part 3
Define
$$I=x_1+x_3+x_4+x_6+x_7+x_9+x_{10}+x_{12}.$$
The indices occurring in $I$ are precisely those congruent to $0$ or $1$ modulo $3$.
Consider any move changing three consecutive vertices.
If the move acts on vertices
$$A_i,A_{i+1},A_{i+2},$$
then among the three indices
$$i,i+1,i+2$$
exactly two are congruent to $0$ or $1$ modulo $3$. Hence the move changes exactly two terms occurring in $I$.
Therefore $I$ changes by
$$2\equiv0\pmod2,$$
so $I$ is invariant.
Initially,
$$I=1.$$
In the target configuration,
$$I=0.$$
Hence the target configuration cannot be obtained.
This completes the proof.
∎
Verification of Key Steps
The delicate point in part 1 is that the parity of minus signs on odd vertices is not itself invariant. A move on six consecutive vertices changes three odd vertices, so that parity flips. The correct invariant is the sum modulo $2$ of two quantities, namely the total parity and the odd-vertex parity. Since both flip simultaneously, their sum remains fixed.
For part 3, the crucial issue is checking every possible triple cyclically. The chosen set of indices is
$${1,3,4,6,7,9,10,12}.$$
The consecutive triples are
$$(1,2,3),(2,3,4),\dots,(12,1,2).$$
Each triple contains exactly two indices from the chosen set:
$${1,3},{3,4},{4},\dots$$
A direct check shows the pattern repeats every three indices:
$$1,0,1,1,0,1,1,0,1,1,0,1.$$
Thus every consecutive triple contributes
$$1+0+1\equiv0\pmod2.$$
If one coefficient were altered, some triple sum would become $1$, and the quantity would cease to be invariant.
Another possible error is forgetting the cyclic nature of the polygon. The triples
$$(11,12,1),\qquad (12,1,2)$$
must also satisfy the invariance condition. For the chosen coefficients,
$$1+1+1\equiv1,\qquad 1+1+0\equiv0.$$
The first computation would contradict invariance if the coefficients were indexed incorrectly. Using the periodic pattern carefully gives
$$c_{11}=0,\quad c_{12}=1,\quad c_1=1,$$
hence
$$0+1+1\equiv0,$$
which is correct.
Alternative Approaches
All three parts may be handled uniformly by linear algebra over $\mathbf F_2$. Each allowed move corresponds to adding a vector in $\mathbf F_2^{12}$. The reachable configurations form an affine subspace generated by these move vectors. One seeks a linear functional annihilating all move vectors but not annihilating the difference between the initial and target configurations.
For six consecutive vertices, the annihilating functional may be chosen with coefficients alternating between $1$ and $0$. For four consecutive vertices, the same functional works directly. For three consecutive vertices, the coefficients satisfy the recurrence
$$c_i+c_{i+1}+c_{i+2}=0,$$
whose nonzero periodic solutions have period $3$.
The invariant method used in the main proof is preferable because it exposes the structure directly and avoids introducing the language of vector spaces and orthogonal complements.