19.18 Инварианты и полуинварианты

При добавлении или исключении буквосочетаний “МО” или “ООММ” разность количества букв “М” и “О” не изменяется, так как в обоих буквосочетаниях равное количество букв “М” и “О”.

С другой стороны, в слове “ММО” разность букв “М” и “О” равна 1, а в слове “ОММО” она равна 0. Значит, эти слова не могут быть синонимами.

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

Пусть за 40 дней на плантации работало не больше 60 человек. Тогда за все время работать вместе могло не больше уникальных пар рабочих. Значит, на плантации должно было работать больше 60 человек.

Изначально количество черных и белых клеток одинаково и четно. За каждое действие, описанное в условии задачи, мы меняем цвета двух клеток.

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

Таким образом, число клеток каждого цвета также будет оставаться четным. Следовательно, на доске не могла остаться одна черная клетка.

При любом действии Даши в начале числа будет стоять единица, следовательно, получить 01 не получится.

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

Но сумма 5 пятерок и 5 четверок равна 45. следовательно, это невозможно.

Заметим, что после таких операций мы не сможем получить число, делящееся на 3. Мы можем получить одно из следующих чисел.

1) Степень двойки, что не делится на 3.

2) Число, полученное перестановкой цифр в степени двойки, у которого сумма цифр не изменится, следовательно, все так же число не будет делиться на 3.

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

Но число 123456 делится на 3, так как сумма его цифр делится на 3. Следовательно, получить его с помощью операций из условия невозможно.

Из условия задачи следует, что путь из А в Б (назовем его АБ) — наибольший. Если составить последовательность АБ, БВ, ВГ и т.д., то она будет убывающей. Но если бы существовал такой город Х, из которого можно было бы вернуться в А, это бы значило, что ХА больше, чем УХ (У — город, из которого мы пришли в Х), что противоречит тому, что последовательность путей убывающая.

а) Заметим, что после каждой такой операции сумма чисел уменьшается на 1. Это происходит, так как все числа не меняются, кроме двух, сумма которых была а стала равной

Следовательно, в какой-то момент сумма чисел станет отрицательной. Значит, среди чисел появится отрицательное число.

б) Заметим, что после каждой такой операции произведение чисел увеличивается. Это происходит, так как все числа не меняются, кроме двух, произведение которых было а стало равным   Следовательно, в какой-то момент на доске будут написаны числа, произведение которых будет больше

Следовательно, хотя бы одно из чисел будет больше 1 000 000.

После такого действия сумма всех чисел в измененном ряду меняется на противоположную (то есть становится положительной), следовательно, уеличивается хотя бы на 2, а в остальных рядах этого типа — не меняется (строки — один тип, столбцы — другой тип). Следовательно, сумма всех чисел в таблице увеличивается. Но тогда процесс не может продлжаться бесконечно, так как сумма чисел во всей таблице не может превосходить сумму модулей всех чисел. Следовательно, этот процесс конечен и через некоторое время мы получим неотрицательную сумму чисел в каждом из рядов.

Пусть число, написанное на доске, равно не делится на 3 или 7. Тогда после каждой операции степень вхождения 3 или 7 в новое число уменьшается на 1. Следовательно, максимум после таких операций мы получим нецелое число.

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

Соединим каждую страну со странами, где правит та же партия, ребрами. Тогда после смены партии в стране А на новую количество ребер между странами, где правит одна и та же партия, увеличивается на 1. Таким образом, этот процесс не может продолжаться бесконечно, так как количество ребер между странами с одной партией не может быть больше, чем количество ребер во всем графе, которое конечно.

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

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

Значит, через несколько шагоьв увеличится. Так как увеличивается, а не увеличивается, наступит момент, когда станет равным

Соединим каждый город с городами, где подняли один и тот же по цвету флаг, ребрами. Тогда после смены цвета флага в городе Х на новый количество ребер между городами, где поднят один и тот же по цвету флаг, увеличивается на 1. Таким образом, этот процесс не может продолжаться бесконечно, так как количество ребер между городами с одинаковыми по цвету флагами не может быть больше, чем количество ребер во всем графе, которое конечно.

Первой сверху карте дадим коэффициент 2, второй — и т.д., у -ой карты коэффициент будет равен . Если карта лежит рубашкой вверх, то ее коэффициент умножаем на 0, если рубашкой вниз — то на 1. Будем считать взвешенную сумму (сумму коэффициентов, умноженных на 0 или 1). Тогда ткапя сумма после каждой операции уменьшается хотя бы на какую-то степень двойки. Меньше нуля она быть не может. Тогда процесс остановится, когда все карты будут лежать рубашкой вверх.

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

Разобьём весь коридор на такие тройки. Количество “занятых” троек не превосходит числа пианистов, и “занятые” тройки не освобождаются, следовательно, пианисты никогда не покидают некоторую ограниченную часть коридора. С другой стороны, сумма квадратов номеров комнат, в которых живут пианисты (с учетом кратности) при каждом переселении возрастает, поскольку . Значит, когда-нибудь переселения прекратятся.

Занумеруем места, на которых стоят фишки, числами от 1 до 100. После выполнения укапзанной операции номер каждой фишки либо не изменится, либо увеличится или уменьшится на 2. Следовательно, фишки, стоящие на четных местах, останутся стоять на четных местах. Таким образом, фишка, стоящая на 100-ом месте, никогда не сможет оказаться на месте с номером 1.

После узхода каждой девочки число платков либо уменьшается, либо увеличивается на 1. Следовательно, после ухода 1-ой девочки число платков будет нечетным, после ухода 2-ой — четным и т.д., после ухода 17-ой — нечетным. Таким образом, мы не сможем получить 10 платков.

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