Математика. Инварианты.

Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого.  В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления.

Задача. На столе стоят вверх дном семь стаканов. Разрешается переворачивать одновременно любые два стакана (разумеется, можно перевернуть любой стакан, стоящий вверх дном, так, чтобы он стоял на дне, а можно перевернуть любой стоящий правильно стакан так, чтобы он стал стоять вверх дном). Можно ли добиться того, чтобы все семь стаканов на столе стояли на дне?

Конечно же, сначала нужно попробовать попереворачивать стаканы. Однако довольно быстро становится понятно, что так просто эта задачка не решается. Тогда возникает желание доказать, что добиться требуемой расстановки стаканов невозможно. Как это сделать? Давайте сравним количества стаканов, стоящих на дне и вверх дном. Сначала мы имеем  стаканов, которые стоят вверх дном и  стаканов, стоящих на дне. Мы можем перевернуть любые два стакана. Какие бы стаканы мы ни выбрали, у нас будет  стаканов вверх дном и  стакана, стоящих правильно. В следующий раз мы можем перевернуть стаканы различными способами. Так, мы можем поставить на дно два стакана, стоящих вверх дном. Тогда у нас останется стакана, стоящих вверх дном, а  стакана будут стоять правильно. Мы можем перевернуть один стакан, стоящий вверх дном, и один стакан, стоящий правильно. Тогда ничего не изменится, и у нас останется  стаканов, стоящих вверх дном, и  стакана, стоящих на дне. И последний вариант: мы можем перевернуть два стакана, которые стоят на дне. Тогда получим исходную ситуацию, а именно  стаканов вверх дном и  стаканов, стоящих правильно.

Давайте посмотрим, что общего во всех этих ситуациях. Найдем разность числа стаканов, стоящих вверх дном, и числа стаканов, стоящих на дне. В исходном варианте эта разность равна семи. После первого переворачивания она становится равна трем. А дальше, в зависимости от выбранного варианта переворачивания стаканов, она станет равной  или . Мы видим, что эта разность может измениться только на . И в данном случае неважно, что исходно мы рассматривали  стаканов, которые были перевернуты вверх дном. Если вы рассмотрите случай, когда  стаканов стоят на дне, а  стаканов — вверх дном, вы придете к тому же самому выводу. В качестве полезного и простого упражнения попробуйте сделать это сами. Предположим, что нам удалось, переворачивая стаканы, добиться их правильного расположения. Тогда в конечной ситуации разность между числом стаканов, стоящих вверх дном, и числом стаканов, стоящих правильно, равна . И мы видим, что число  отличается от на  — это число не кратно . Следовательно, действуя описанным в условии задачи способом, добиться того, что все  стаканов будут стоять на дне, невозможно.

А теперь вернемся к непонятному слову инвариант. Оно имеет очень простое значение: то, что сохраняется, не изменяется при некоторых преобразованиях.

В рассмотренной задаче инвариантом был остаток от деления на  разности числа стаканов, стоящих вверх дном, и числа стаканов, стоящих на дне. Он должен всегда оставаться равным .