Задача
COM-B2-M05-P008 Знаки на цикле
#8
★★★☆☆ Уровень 3 из 5
На вершинах цикла из \(9\) вершин стоят знаки. За ход можно выбрать ребро цикла и поменять знаки в обеих его концах. Сначала ровно одна вершина имеет знак \(-\). Докажите, что нельзя сделать все знаки положительными.
Произведение всех знаков сохраняется.
Один ход меняет ровно два знака, значит, произведение всех знаков умножается на \((-1)^2=1\). Поэтому произведение является инвариантом.
В начале произведение равно \(-1\), так как отрицательный знак один. В состоянии, где все знаки положительны, произведение равно \(1\). Инвариант различен, значит, такое состояние недостижимо.
Здесь графовая форма ещё проста; позже она усилится до критерия достижимости.