На острове Серобуромалин обитают 13 серых, 15 бурых и 17 малиновых хамелеонов. Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий (серый и бурый становятся оба малиновыми и т. д.). Может ли случиться так, что через некоторое время все хамелеоны будут одного цвета?
Ответ: не может. Мы должны доказать, что из тройки $(13,15,17)$ с помощью операций, описанных в условии, т. е. увеличения одного из чисел на 2 и одновременного уменьшения двух других на 1 (если они положительны), нельзя получить ни одну из троек $(45,0,0)$, $(0,45,0)$ и $(0,0,45)$ ($45=13+15+17$). Как и в большинстве аналогичных задач с отрицательным ответом, для доказательства надо постараться подобрать инвариант — величину, определённую на тройках целых чисел $(\textit{с},\textit{б},\textit{м})$ и не меняющуюся при указанных преобразованиях троек, которая бы принимала разные значения для первой тройки и трёх последних.
Таким инвариантом является, например, остаток $r$ от деления на 3 разности $\textit{с}-\textit{б}$ первых двух чисел тройки $(\textit{с},\textit{б},\textit{м})$.
Действительно, при «смене окраски хамелеонов» числа $\textit{с}$ и $\textit{б}$ могут замениться на $\textit{с}-1$, $\textit{б}-1$; на $\textit{с}+2$, $\textit{б}-1$ или на $\textit{с}-1$, $\textit{б}+2$; в первом случае $\textit{с}-\textit{б}$ не меняется, в двух других — изменяется на 3, значит, остаток $r$ остаётся прежним. Остаётся заметить, что для исходной тройки $(13,15,17)$ он равен 1, а для трёх последних $r=0$.
Рис. 1Рис. 2
Несложно ответить и на общий вопрос — при каком условии из одной тройки чисел нашими операциями можно получить другую. Поскольку сумма $s=\textit{с}+\textit{б}+\textit{м}$ всех чисел тройки, очевидно, тоже инвариант, мы можем воспользоваться удобной и красивой геометрической интерпретацией нашей задачи: каждую тройку $(\textit{с},\textit{б},\textit{м})$ с заданной суммой $s$ будем изображать точкой внутри равностороннего треугольника высоты $s$, удалённой от его сторон на расстояния $\textit{с}$, $\textit{б}$, $\textit{м}$ соответственно (рис. 1). При этом каждой нашей операции отвечает сдвиг точки в треугольнике на расстояние 2 перпендикулярно одной из сторон. Разобьём треугольник на $s^2$ одинаковых правильных треугольников высоты 1 (рис. 2); очевидно, их вершины отвечают всем целочисленным тройкам с заданной суммой $s$. Возьмём одну из этих вершин, проведём из неё стрелки в те точки, куда её можно сдвинуть с помощью наших операций, из концов стрелок проведём новые стрелки и т. д. Все эти стрелки образуют ещё одну сеть правильных треугольников со стороной 2. Их вершины изображают все тройки чисел, которые можно получить из исходной перекрашиванием хамелеонов. Легко убедиться, что из любой красной точки за исключением вершин большого треугольника можно перейти по красным стрелкам в любую другую. Остальные точки аналогичным образом разобьются ещё на два класса «связанных» точек (зелёные и синие на рис. 2; стрелки для них не показаны). Значение инварианта $r$ для всех точек одного класса будет, разумеется, одним и тем же; причём легко проверить, что для красных точек $r=0$, для зелёных — $r=1$, для синих — $r=2$.
Таким образом, из тройки $(\textit{с},\textit{б},\textit{м})$ можно получить другую тройку $(\textit{с}',\textit{б}',\textit{м}')$ тогда и только тогда, когда в первой тройке хотя бы два числа положительны и значения инвариантов $s$ и $r$ для данных троек совпадают (значения любого другого инварианта будут совпадать уже автоматически; докажите непосредственно, что, например, остаток от деления $\textit{м}-\textit{б}$ на 3 выражается через $s$ и $r$). В частности, если $s$ кратно 3, для всех вершин большого треугольника $r=0$, т. е. они достижимы только из точек с $r=0$ (на рис. 2 — из красных точек); если же $s$ не делится на 3, то в одной из них будет $r=0$, в другой — $r=1$, в третьей — $r=2$, т. е. из любой точки $(\textit{с},\textit{б},\textit{м})$ можно попасть в одну (и только одну) вершину.
