Всем привет!

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

 Задача 1. В алфавите языка племени УЫУ всего две буквы: У и Ы, причём этот язык обладает такими свойствами: если из слова выкинуть стоящие рядом буквы УЫ, то смысл слова не изменится. Точно так же смысл слова не изменится при добавлении в любое место слова буквосочетания ЫУ или УУЫЫ. Можно ли утверждать, что слова УЫЫ и ЫУУ имеют одинаковый смысл?

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

Задача 2. На доске написаны числа 1, 2, …, 37. Разрешается стереть любые два числа и вместо них написать их разность. Повторив эту операцию 36 раз, мы получим одно число. Может ли это число быть нулём?

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

На этот вопрос есть два возможных ответа: или «да, может», или «нет, не может». Причем если мы доказываем ответ «да», то нужно привести пример, когда ноль достигается. Если же нет – нужно доказать, что как бы мы не действовали, нуля мы не получим. Можно, конечно, попробовать, но мне что-то не улыбается делать 36 вычитаний (хотя бывают задачи, в которых как раз и нужно описать подобную конструкцию). Попробуем доказать, что ноль не получится. Для этого отметим такую закономерность. Я утверждаю, что если мы вычитаем из чётного числа чётное, то получится чётное, не правда ли? При вычитании из нечётного нечётное – тоже получится чётное. А при вычитании из нечётного чётное или наоборот, мы получаем нечётное. Запишем это в такую таблицу:

Ч, Ч -> Ч

Ч, Н -> Н

Н, Ч -> Н

Н, Н -> Ч

А теперь давайте поищем инвариант. Можно заметить, что количество нечётных чисел в первых трёх случаях не меняется, а в четвёртом – уменьшается на 2. Но тогда чётность количества нечётных чисел – инвариант! Переварили? Звучит сложновато, согласен. Но так и есть: чётность их количества не меняется. При этом нам надо, чтобы нечётных чисел не стало вовсе: ноль ведь чётное. А сколько было нечётных исходно? Давайте считать: от 1 до 38 есть 19 пар чисел, значит, 19 чётных и 19 нечётных. Убираем 38 – нечётных всё равно 19. Нечётное количество нечётных чисел! Вспомнив про наш инвариант, замечаем, что в конце тогда должно остаться именно нечётное число, а не 0. Победа!

Кстати, эта задача решалась и иначе. Заметим, что разность двух чисел имеет ту же чётность, что и их сумма. Действительно, (a – b) и (a + b)  отличаются на 2b, то есть на чётное число – а значит разность и сумма одной чётности. Но тогда с точки зрения чётности нам не важно, вычитаем мы из числа другое или складываем их. Прекрасно, будем складывать! А тогда мы знаем, что сумма всех чисел на доске – инвариант, и значит, последнее число с точки зрения чётности совпадет с чётностью суммы исходных 37 чисел. А эта сумма нечётна – например, потому, что в ней нечётное количество нечётных чисел. Значит, и в конце будет нечётное число, то есть не ноль.

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

Решение. Эта задача очень сложна, если не знать принцип работы с полуинвариантами. Сейчас мы опишем процесс искомого разбиения. Для начала – первый важный приём – разобьём парламент «абы как», просто на две любые палаты. Теперь посчитаем количество «недружб» между членами каждой палаты. Скажем, если в первой палате есть два враждующих депутата, то добавляем к сумме 1, затем делаем так для каждой враждующей пары из первой палаты, а потом аналогично – для второй. В итоге мы получим некоторое число «недружб» в сумме для обеих палат.

Далее – второй приём – рассмотрим произвольного депутата, у которого есть хотя бы два врага в его палате (если таких нет – мы решили задачу, так как у каждого не более одного врага). Раз у выбранного депутата всего не более трёх врагов, и при этом хотя бы два из них находятся с ним в одной палате, то в другой палате остаётся не более одного его врага. Тогда давайте переведём нашего депутата из его нынешней палаты в другую! Понятно, что при этом у нас количество «недружб» уменьшится – мы убрали как минимум две «недружбы» из его бывшей палаты, добавили не более одной в новой палате, а остальных мы не трогали. Теперь рассмотрим следующего депутата, у которого по крайней мере два врага в его палате. И так далее! С каждой такой перестановкой суммарное количество «недружб» будет уменьшаться. Но не может же оно уменьшаться до бесконечности! Значит, когда-то этот процесс закончится. А когда он закончится? Когда нам больше некого будет перемещать из палаты в палату, то есть, когда у каждого будет не более одного врага с ним в палате. Что и требовалось!

Ну как вам решение? Не отпускает ощущение, что где-то обманули, но где – не понять? Согласен, на первый взгляд кажется, что мы не решили задачу, а просто написали какие-то слова. На самом деле мы предъявили чёткий алгоритм, работа которого приведёт нас к искомому результату. А помог нам в этом полуинвариант – суммарное количество «недружб»: эта величина только уменьшалась, но при этом была ограничена снизу (это количество никак не может стать отрицательным), а значит процесс получился конечным. Вот такая задачка. Она весьма непростая, так что если вы её не поняли с первого раза – не беда, посмотрите этот урок через некоторое время, и все уляжется! И конечно, не забудьте решить похожую задачу № 3 из теста по следам урока!

До встречи!

 1.          Дополнительная информация           

Рекомендуемые тренажёры:

1. В алфавите языка племени Мумбо-Юмбо всего две буквы: М и Ю, причем этот язык обладает такими свойствами: если из слова выкинуть стоящие рядом буквы ЮМ, то смысл слова не изменится. Точно так же смысл слова не изменится при добавлении в любое место слова буквосочетания МЮМЮ или ЮМЮМ. Можно ли утверждать, что слова МЮММ и ЮМЮЮ имеют одинаковый смысл? Ответ: нет.

2. На доске написаны числа 0, 1, 0, 0. За один шаг разрешается прибавлять единицу к любым двум из них. Можно ли, повторяя эту операцию, добиться, чтобы все числа стали равными?  Ответ: нет.

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

 Рекомендуемые тесты:

1. В языке Древнего Племени алфавит состоит всего из двух букв: «М» и «О». Два слова являются синонимами, если одно из другого можно получить при помощи исключения или добавления буквосочетаний «МО», «OО» и «ММ», повторяемых в любом порядке и любом количестве. Являются ли синонимами в языке Древнего Племени слова «ОММ» и «МОО»?  Ответ: нет.

2. Рита, Люба и Варя решали задачи. Чтобы дело шло быстрее, они купили конфет и условились, что за каждую решённую задачу девочка, решившая её первой, получает четыре конфеты, решившая второй  – две, а решившая последней  – одну. Девочки говорят, что каждая из них решила все задачи и получила 20 конфет, причём одновременных решений не было. Они ошибаются. Как вы думаете, почему?

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