Задача
COM-B2-M05-P006 Три цвета камней
Есть \(20\) красных, \(21\) синий и \(22\) зелёных камня. За ход выбирают два камня разных цветов, убирают их и добавляют два камня третьего цвета. Докажите, что невозможно получить состояние, в котором все камни одного цвета.
Посмотрите на разности чисел камней двух цветов по модулю \(3\).
Обозначим числа красных, синих и зелёных камней через \(r,b,g\). При ходе, например, \(r\) и \(b\) уменьшаются на \(1\), а \(g\) увеличивается на \(2\). Разность \(r-b\) не меняется, а разности \(b-g\) и \(g-r\) меняются на кратные \(3\). Поэтому остатки всех попарных разностей по модулю \(3\) сохраняются.
В начале \(r-b=20-21=-1\), то есть \(r-b\equiv 2\pmod 3\). Если бы все камни стали одного цвета, то две из величин \(r,b,g\) были бы равны \(0\), а третья — \(63\), поэтому разности были бы кратны \(3\). Противоречие.
Хорошая задача на неочевидный модульный инвариант.