Задача
COM-B1-M06-P023 Операция с тремя числами
Дана тройка \((1,1,1)\). За ход можно прибавить \(2\) к двум числам и вычесть \(1\) из третьего. Можно ли получить \((10,10,10)\)?
Посмотрите на сумму по модулю \(3\).
За ход сумма меняется на \(2+2-1=3\), значит её остаток по модулю \(3\) сохраняется. В начале сумма \(3\equiv0\pmod3\). В конце сумма \(30\equiv0\pmod3\), этот инвариант не запрещает. Попробуем сумму квадратов по модулю \(3\): числа \(1\) и \(10\) сравнимы по модулю \(3\), а операция меняет остатки двух чисел на \(-1\) и одного на \(-1\), то есть все три остатка уменьшаются на \(1\). После каждого хода все три числа остаются равными по модулю \(3\). В начале они все \(1\), в конце \(10\equiv1\), инвариант тоже не запрещает. Значит по этим инвариантам запрета нет; действительно, состояние достижимо: применим ход три раза, каждый раз вычитая из разной координаты, все координаты увеличатся на \(3\). Повторив три таких цикла, получим \((10,10,10)\).
Полезная задача: не каждый инвариант должен запрещать, иногда нужно увидеть достижимость.