Задачи на инвариант

Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики.

Задачи на инвариант — олимпиадные задачи, в которых нечто остается неизменным при тех или иных преобразованиях.^[1][2]

Примеры задач

Задача: На шахматной доске стоит черный слон и белая ладья. Белые, как водится, ходят первыми. Доказать, что при правильной игре черные никогда не выиграют.

Решение: Слон всегда останется на полях одного цвета (это и есть инвариант данной задачи). Поэтому если ладья каждым своим ходом будет останавливаться на поле другого цвета, её невозможно будет побить.

Задача: На доске написаны числа 2, 6, -5, 3. Разрешается: 1) за раз увеличить любое из этих чисел на 2 и уменьшить любое другое на 6; 2) за раз увеличить любое из этих чисел на 3, увеличить любое другое на 1 и увеличить любое третье на 4. Проделывая в любом порядке эти 2 операции (если нужно, многократно), уравняйте написанные на доске числа. Или - докажите, что сделать это невозможно.

Решение: Мы можем проделывать операции (1) и (2) сколько угодно раз и в любом порядке - уравнять числа на доске нам не удастся. Но как доказать, что попытки уравнять числа на доске тщетны? Вот тут-то нам и пригодится понятие "инвариант". В данном конкретном случае инвариантом будет остаток от деления на 4 суммы записанных на доске чисел. Операция (1) уменьшает сумму записанных на доске чисел на 4. Операция (2) увеличивает сумму записанных на доске чисел на 8. Значит, обе эти операции не изменяют остаток от деления суммы записанных на доске чисел на 4. У исходной комбинации чисел остаток от деления суммы чисел на 4 равен 2. Если все 4 числа равны друг другу, то остаток от деления суммы чисел на 4 равен 0. Это и доказывает, что операциями (1) и (2) уравнять записанные на доске числа нельзя.

Примечания

1. ↑ Ионин Ю., Курляндчик Л. Поиск инварианта // Квант. — 1976. — № 2.
2. ↑ Толпыго А. Инварианты // Квант. — 1976. — № 12.

Ссылки

• Примеры задач на инвариант
• Инварианты в задачах по математике и программированию