Problem
COM-B2-M05-P008 Signs on a Cycle
#8
★★★☆☆ Level 3 of 5
Signs are written at the vertices of a cycle with \(9\) vertices. In one move, choose an edge of the cycle and change the signs at both its endpoints. Initially exactly one vertex has sign \(-\). Prove that it is impossible to make all signs positive.
The product of all signs is preserved.
One move changes exactly two signs, so the product of all signs is multiplied by \((-1)^2=1\). Therefore the product is an invariant.
Initially the product is \(-1\), because there is one negative sign. In the all-positive state, the product is \(1\). The invariant differs, so the state is unreachable.
The graph form is still simple here; later it is strengthened to a reachability criterion.