Начинаем разбираться в инвариантах

На прошлой неделе на курсе математики я столкнулся с понятием инварианта. Честно говоря, для большей части задач я не понял, как что-то доказать, и ловил себя на том, что просто перебираю варианты или угадываю ответ. Но в математике так нельзя – доказательство не должно браться «с потолка».

В этой статье я попробую структурировать (в первую очередь для того, чтобы самому лучше разобраться) информацию по инвариантам и разберу одну из классических задач.

Виды задач на инварианты

Задачи на инварианты можно условно разбить на два вида:

1. требуется доказать некий инвариант, т.е. он явно определен;
2. инвариант используется при решении и сразу не очевиден.

В некоторых задачах по математике дается разрешенный набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое?

Если задача небольшая, то перебором вариантов легко убедиться в правильности ответа “можно/нельзя”, однако обосновать этот ответ бывает трудно. Инвариант является тем методом, который позволяет во многих случаях решать доказательную часть таких задач.

Что такое инвариант?

Говоря простым языком, инвариант – это некоторая величина или свойство, которое не меняется при разрешенных в задаче преобразованиях. Это может быть сумма чисел, их произведение, четность, остаток от деления, цвет клетки и так далее.

В математике это определение звучит строже:

Инвариант – это свойство математического объекта, остающееся неизменным при разрешенных преобразованиях.

Разрешенные преобразования в каждой задаче свои, и главная трудность часто заключается именно в том, чтобы найти то самое неизменное свойство.

Основное правило задач с инвариантами

Суть метода можно сформулировать так:

Если значение инварианта в двух состояниях объекта различно, то одно состояние нельзя получить из другого.

Это правило мы и будем применять.

В задачах школьного уровня в качестве инварианта чаще всего используется четность чисел или остаток от деления.

Давайте вспомним, что такое четность:

Четность – это свойство целого числа быть

• четным (делиться на 2 без остатка: 0, 2, 4…);
• нечетным (давать остаток 1 при делении на 2: 1, 3, 5…).

Теперь перейдем к практике.

Задача 1. Число и 16 учеников

Условие. На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу (как хочет). Может ли в результате получиться число 0?

Решение. Математический способ решения этой задачи подразумевает, что мы должны железобетонно доказать возможность или невозможность получение нуля из исходного числа 11 в процессе передачи листа через 16 учеников.

Давайте рассуждать. У нас есть:

• Исходное число: 11 (нечетное).
• Целевое число: 0 (четное).
• Количество ходов (преобразований): 16 (четное).
• Разрешенное преобразование: прибавить 1 или отнять 1.

Если мы запишем 16 последовательных состояний числа на листке бумаги при разрешенных преобразованиях (прибавить или отнять 1), то от исходного числа 11 может образоваться следующая цепочка чисел:

12→11→10→9→8→7→6→5→4→3→2→1→0→1→0→-1

Что происходит с четностью числа за один ход? Если мы прибавляем 1 к нечетному числу, оно становится четным (11→12). Если отнимаем 1 от нечетного – тоже становится четным (11→10). И наоборот, прибавляя или отнимая 1 от четного числа, мы получаем нечетное. То есть каждый ход обязательно меняет четность числа.

Теперь посмотрим на цепочку выше. После первого хода число становится четным, после второго – снова нечетным, после третьего – четным и так далее. Нетрудно заметить закономерность: после четного количества ходов четность числа совпадает с исходной.

У нас 16 ходов – число четное. Значит, после 16 ходов число должно быть той же четности, что и в начале, то есть нечетным.

Число 0 – четное. Следовательно, какими бы ни были действия учеников (прибавляли они единицу или отнимали), получить 0 из 11 за 16 ходов невозможно.

Ответ: нет, не может.

Какой инвариант мы использовали? Инвариантом в этой задаче является четность числа на листке при четном числе ходов (как было сказано выше, через четное число ходов четность возвращается к исходной). Это позволило нам сравнить начальное и конечное состояния.

Что дальше?

В следующей статье мы продолжим решать задачи на инварианты, а пока предлагаю решить похожую задачу самостоятельно для закрепления:

Задание. Можно ли, имея 8 листов бумаги, некоторые из них разрезать на 4 части, потом некоторые из получившихся листов снова разрезать на 4 части и так далее, получить ровно 50 листов?

Подсказка: подумайте, что происходит с общим количеством листов при каждом разрезании и найдите величину, которая остается неизменной.