Метод инвариантов: что не меняется при преобразованиях
Инвариант — это величина или свойство, которое остается неизменным при выполнении определенных операций. Поиск инварианта является ключевой идеей при решении многих задач на алгоритмы и процессы.
Классический пример — четность. Если на доске написаны числа и разрешается стирать любые два и писать вместо них их сумму, то сумма всех чисел на доске не меняется (или меняется предсказуемо, в зависимости от условия). Четность суммы — простейший инвариант.
В более сложных задачах инвариантом может быть остаток от деления на определенное число (модулярная арифметика) или раскраска. Например, задачи о шахматной доске часто решаются через стандартную черно-белую раскраску. Если фигура (например, конь) всегда меняет цвет поля при ходе, то за нечетное число ходов он не может попасть на поле того же цвета.
Существуют и полуинварианты — величины, которые меняются монотонно (всегда возрастают или всегда убывают). Они полезны для доказательства конечности процессов или отсутствия зацикливания. Этот метод часто применяется в компьютерных науках и дискретной математике.
