Распечатать запись Распечатать запись

Полуинвариант

Наряду с задачами на инвариант, на олимпиадах довольно часто встречаются и задачи на полуинвариант. Полуинвариант — это некоторая величина, которая в отличие от инварианта не остается неизменной, а увеличивается или уменьшается и может принимать при этом лишь конечное число различных значений.

Лучше всего рассмотреть, как решать такие задачи, на примерах.

Задача 1. В квадрате 20\times20 стоят 400 ненулевых чисел. Можно изменить знак у всех чисел, стоящих в одном столбце или в одной строке. Докажите, что за конечное число таких операций можно добиться того, что сумма чисел, стоящих в любой строке или в любом столбце, будет неотрицательной.

Решение. Полуинвариантом здесь будет сумма всех чисел в таблице. Пусть сумма чисел, стоящих в каком-либо столбце или в какой-либо строке, отрицательна. Поменяем знак у всех этих чисел. Тогда сумма всех чисел в таблице увеличится. Однако эта сумма может принимать лишь конечное число значений — все они получаются расстановками знаков “плюс’’ и “минус’’ перед числами таблицы. Поэтому на каком-то шаге сумма всех чисел перестанет расти. Такая сумма и даст требуемую таблицу.

Задача 2. У каждого члена парламента не более трех врагов. Докажите, что парламент можно разбить на две палаты так, что у каждого его члена в одной с ним палате будет не более одного врага.

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

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

Решение. В качестве инварианта рассмотрим сумму всех чисел на окружности. Ясно, что после каждого шага она может только уменьшиться, если не все числа равны, и остаться неизменной, если все числа равные. Кроме того, эта сумма неотрицательна. Следовательно, она может принимать только конечное число значений. Когда сумма чисел перестанет уменьшаться, мы получим равные числа.

А теперь несколько задач для самостоятельного решения.

1. На плоскости даны 2n точек. Докажите, что эти точки можно соединить n попарно не пересекающимися отрезками.

Показать решение

2. По кругу стоят дети, у каждого из которых есть конфеты. По сигналу ведущего каждый передает половину своих конфет соседу справа (если у кого-то из детей нечетное число конфет, то ведущий сначала дает ему еще одну конфету). Докажите, что через какое-то число таких передач у всех детей конфет станет поровну.

Показать решение

3. Задано несколько красных и несколько синих точек. Какие-то из этих точек соединены отрезками. Точка называется особой, если более половины соединенных с ней точек имеют цвет, отличный от ее цвета. Если есть хотя бы одна особая точка, то выбирается любая особая точка и перекрашивается в другой цвет. Докажите, что через конечное число шагов не останется ни одной особой точки.

Показать решение

4. Непустые конечные множества A_1,A_2,A_3,\ldots состоят из целых чисел, причем при n\ge2 каждый элемент множества A_n является средним арифметическим двух или более элементов множества A_{n-1}. Докажите что в этой последовательности конечное число множеств.

Показать решение

Один комментарий

  1. 1 Инвариант | Математика, которая мне нравится:

    [...] Читайте также о полуинварианте. [...]

Оставьте свой отзыв

Добавить изображение