Задачи на инвариант — олимпиадные задачи, в которых нечто остается неизменным при тех или иных преобразованиях.[1][2]
Задача: На шахматной доске стоит черный слон и белая ладья. Белые, как водится, ходят первыми. Доказать, что при правильной игре черные никогда не выиграют.
Решение: Слон всегда останется на полях одного цвета (это и есть инвариант данной задачи). Поэтому если ладья каждым своим ходом будет останавливаться на поле другого цвета, её невозможно будет побить.
Задача: Ребёнок овладел всего лишь двумя звуками: "У" и "А", причем два слова в лексиконе этого ребёнка означают одно и то же, если одно получается из другого при помощи следующих преобразований: исключения идущих подряд звуков "УА" или "ААУУ" и добавления в любое место сочетания "АУУА". Докажите, что слова "ААУАААУУА" и "ААУУААА" означают одно и то же.
Решение: Нетрудно проверить, что второе слово получается из первого в результате последовательного применения трёх преобразований, указанных выше (назовём их смыслосохраняющими преобразованиями) — надо только найти эту цепочку смыслосохраняющих преобразований. Однако, на вопрос, означают ли слова "АУУ" и "УАА" одно и то же, ответить гораздо сложнее. Перебор последовательностей смыслосохраняющих преобразований не позволит получить второе слово из первого, так как данные слова имеют разный смысл. Для доказательства этого нужен принципиально другой подход, именуемый поиском инварианта.
Задачи на инвариант.