Идеи и методы решения нестандартных задач: инварианты

Инварианты

Инвариант – величина, которая не изменяется в результате некоторых операций (например, разрезание и перестановка частей фигур не меняет суммарной площади). Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться чётность или раскраска. В задачах про сумму цифр используются остатки от деления на 3 или 9. Полуинвариант – величина, изменяющаяся только в одну сторону (т. е. которая может только увеличиваться или только уменьшаться). Понятие полуинварианта часто используется при доказательствах остановки процессов.

Пример 1. На чудо-яблоне растут бананы и ананасы. За один раз разрешается сорвать с неё два плода. Если сорвать два банана или два ананаса, то вырастет ещё один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если известно, сколько бананов и ананасов росло вначале?

Решение. Чётность числа бананов не меняется, поэтому, если число бананов было чётным, то оставшийся плод – ананас, если число бананов было нечётным, то – банан.

Пример 2. В одной клетке квадратной таблицы 4 × 4 стоит знак минус, а в остальных стоят плюсы. Разрешается одновременно менять знак во всех клетках, расположенных в одной строке или в одном столбце. Докажите, что, сколько бы мы ни проводили таких перемен знака, нам не удастся получить таблицу из одних плюсов.

Решение. Заменим знак «+» на число 1 и знак «−» на число −1. Заметим, что произведение всех чисел в таблице не меняется при смене знака у всех чисел столбца или строки. В начальном положении это произведение равно −1, а в таблице из одних плюсов +1, чем и доказана невозможность перехода.

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

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

Пример 4. На острове Серобуромалин живут хамелеоны: 13 серых, 15 бурых и 17 малиновых. Если два хамелеона разных цветов встречаются, то они оба меняют свой цвет на третий. Может ли случиться, что в некоторый момент все хамелеоны на острове станут одного цвета?

Указание. Обозначим количества хамелеонов каждого цвета Б, С и М соответственно. Докажите, что остатки от деления на 3 разностей Б – С, С – М и М – Б не меняются.

Пример 5. На 44 деревьях, расположенных по кругу, сидели по одному веселому чижу. Время от времени какие-то два чижа перелетают один по часовой стрелке, а другой – против, каждый – на соседнее дерево. Могут ли все чижи собраться на одном дереве?

Решение. Пронумеруем деревья по кругу от 1 до 44. Сумма номеров деревьев, на которых сидят чижи, либо не меняется, либо уменьшается на 44, либо увеличивается на 44. Тем самым, остаток от деления этой суммы номеров на 44 не меняется. Изначально этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не смогут собраться на одном дереве.

Пример 6. Можно ли круг разрезать на несколько частей, из которых сложить квадрат? (Разрезы – это участки прямых и дуги окружностей.)

Решение. Рассмотрим инвариант: разность сумм длин вогнутых и выпуклых граничных дуг всех частей. Эта величина не изменяется при разрезании одной части на две и при складывании одной части из двух. Для единичного круга этот инвариант равен 2, а для квадрата – нулю. Поэтому «квадратура круга» невозможна.

Задачи для самостоятельного решения

1. Можно ли разрезать выпуклый 17-угольник на 14 треугольников?

2. Можно ли круг разрезать на несколько частей и сложить из них квадрат? (Разрезы – это прямые и дуги окружностей.)

3. Болельщик Вася нарисовал расположения игроков на футбольном поле к началу первого и второго таймов. Оказалось, что некоторые игроки поменялись местами, а остальные остались на своих местах. При этом расстояние между любыми двумя игроками не увеличилось. Докажите, что все эти расстояния не изменились.

4. Докажите, что сумма квадратов расстояний от вершин правильного n-угольника до любой прямой, проходящей через его центр есть величина постоянная.

5 (сизифов труд). На горе 1001 ступенька, на некоторых лежат камни, по одному на ступеньке. Сизиф берет любой камень и переносит его вверх на ближайшую свободную ступеньку (т. е. если ближайшая ступенька свободна, то на неё, а если она занята, то на несколько ступенек вверх до первой свободной). После этого Аид скатывает на одну ступеньку вниз один из камней, у которых предыдущая ступенька свободна. Камней 500 и первоначально они лежали на нижних 500 ступеньках. Сизиф и Аид действуют по очереди начинает Сизиф. Цель Сизифа положить камень на верхнюю ступеньку. Может ли Аид ему помешать?

6. Столица страны соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с 10 городами (если A соединён с B, то B соединён с A). Известно, что из любого города можно попасть в любой другой (может быть, с пересадками). Докажите, что можно закрыть половину авиалиний, идущих из столицы, так что возможность попасть из любого города в любой другой сохранится.

7. Во время перемирия за круглом столом разместились рыцари из двух враждующих станов. Оказалось, что число рыцарей, справа от которых сидит враг, равно числу рыцарей, справа от которых сидит друг. Докажите, что число рыцарей делится на 4.

8. В одном бидоне находится 1 л воды, а в другом – 1 л спирта. Разрешается переливать любую часть жидкости из одного бидона в другой. Можно ли добиться, чтобы в первом бидоне концентрация спирта оказалась больше 50%?

9. Круг разрезали на части и сложили выпуклую фигуру. Докажите, что это опять круг. (Разрезы – это участки прямых и дуги окружностей.)

10. Можно ли разрезать правильный треугольник на части и сложить квадрат, если части можно параллельно переносить, но не поворачивать?