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

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

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

Всего у каждого из семи подписанных на канал учеников может быть не более трёх хороших друзей. Следовательно, изначально количество хороших пар не превышает 21. Рассмотрим момент, когда на канал подписались все ученики, кроме одного. Тогда в момент, когда подпишется последний ученик, количество хороших пар уменьшится уже на 3, следовательно, подписок может быть не более чем 19. Так как в классе всего 28 человек, то весь класс не может быть подписан на канал.

Пронумеруем все единицы, начиная с самой левой, натуральными числами от до Единице с номером поставим число где — количество нулей, которые находятся правее нее. Рассмотрим величину

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

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

Возьмём произвольное слово длины и будем последовательно передвигать в нем буквы A, не уменьшая при этом крутизну слова. Ясно, что в нашем слове должно быть хотя бы две буквы B, иначе крутизна слова равна Далее, предположим, что в слове между двумя буквами В есть буква А, т.е. слово имеет вид …В … …В …Посмотрим, с какой стороны от буквы больше букв А, и передвинем выделенную букву в тот конец слова, где их меньше. Заметим, что при таком перемещении буквы А мы могли разрушить лишь слова вида ABBA и ABBA, которые давали вклад в размер крутизны исходного слова. Предположим, что мы переместили букву К налево. Тогда слова вида BBA сохранились, а вместо слов вида ABB образованных буквой В слева от и двух букв В и буквы мы получим как минимум столько же слов, которые образуются из нашей передвинутой буквы двух любых букв У и любой буквы А, которая стояла в исходном слове справа от буквы А. Получается, что мы можем рассматривать только слова вида А...АВ...ВА...А. Если в левом блоке будет букв А, а в правом букв А, то крутизна такого слова равна

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

Таким образом, можно считать, что или причем (иначе в нашем слове не будет или букв А, или букв В). Теперь возьмем слово, в котором и заменим последнюю букву В на букву А. При такой замене крутизна слова изменится на величину

Значит, при крутизна слова после такой замены увеличивается, а при уменьшается. Аналогично, посмотрим, что произойдёт, если в слове, в котором заменить первую букву В на букву A:

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

Замечание.

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

Пусть сумма всех чисел на данный момент равна После применения операции она станет равна

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

Рассмотрим сумму квадратов выписанных чисел. После применения указанной операции она становится равной

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

Пусть Если пара заменится на пару а если пара заменится на пару В первом случае сумма чисел пары уменьшилась с на а во втором сумма заменилась на что меньше при и равно при Поскольку сумма остается натуральной, рано или поздно процесс должен прекратиться или зациклиться. Он может прекратиться только если операцию нельзя выполнить. Это означает, что одно число вдвое меньше другого. Зацикливание же возможно только если сумма перестанет уменьшаться, а это может случиться только если числа станут равными.

Будем считать школьников вершинами, а вражду — ребрами. Обозначим за и количество внутренних ребер в первой группе и второй группе соответственно. Рассмотрим величину Легко понять, что при любом переводе данная величина уменьшится (хотя бы на 1), но уменьшаться бесконечно она не может, поэтому в какой-то момент процесс остановится.

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

Лемма. Докажем, что для любого начального набора чисел существует число такое, что на доске никогда не появится числа больше, чем

Доказательство. Рассмотрим произвольную пару которую стерли в некоторый момент времени. Без ограничений общности можем считать, что тогда при некотором Рассмотрим функцию

Легко проверить, что на отрезке решение уравнения единственно (для этого можно решить квадратное это уравнение). Далее рассмотрим два случая:

Если то следовательно,

то есть большое из чисел пары не увеличилось.

Если то

Наконец, если — максимальное число начального набора, то на доске никогда не появится числа, которое было бы больше, чем

______________________________________________________________________________________________________________________________________________________

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

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

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

Рассмотрим граф Каждому городу страны сопоставим вершину данного графа. Соединим ребрами те и только те вершины, которые соответствуют городам, расстояние между которыми не превосходит км. Будем красить вершину в цвет флага над ратушей соответствующего города.

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

Таким образом, не позже чем, через дней данный процесс закончится.

Рассмотрим произвольный вырезаемый куб . Если наименьшее число обозначить , то остальные числа будут , . Значит, их сумма , то есть имеет остаток 4 от деления на 8. Значит, вырезание кубиков либо сохраняет суммарный остаток от деления на 8, либо изменяет его на 4. Осталось узнать, чему этот остаток равнялся изначально. Сумма чисел от 1 до 343 равна их среднему арифметическому на их количество 343. 172 делится на 4 , но не на 8 , а 343 нечётно, поэтому исходный остаток равен 4.

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

Давайте рассмотрим на количество пар враждующих между палатами. Заметим, что оно увеличивается. Действительно, для того чтобы депутат сделал переход из палаты А в палату Б, у него в палате А должно быть хотя бы 2 врага, тогда между палатами у него не больше 1 врага (так как всего не больше 3-х врагов). После его перехода между палатами у него стало хотя бы 2 вражды. Значит, количество враждующих пар между палатами увеличивается. Общее количество пар врагов число конечно, количество пар врагов между палатами не может его перерасти, поэтому в какой-то момент переходы прекратятся.

Для каждой кучки назовём её показателем максимальную степень двойки, на которую делится число содержащихся в ней камней, она может быть равна . Рассмотрим поведение показателей кучек, участвующих в перекладывании. После перекладывания камней из кучки с камнями в кучку с камнями в первой остаётся камней, а во второй становится камней. Если , то

поэтому оба показателя возрастут. Если , то

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Докажем по индукции, что после перекладываний количества камней в кучках имеют вид

для некоторого целого числа .

База индукции при очевидна:

то есть .

Шаг индукции: либо мы перекладываем камни из правой кучки в левую, тогда в левой станет , а в правой останется камней, при этом , либо мы перекладываем камни из левой кучки в правую, тогда в левой останется , а в правой станет камней, при этом .

Если после некоторого -ого перекладывания раскладки останется всего одна кучка, то число камней в другой станет равным 0 , следовательно, выполнится равенство одно из равенств или . В обоих случаях N будет делителем числа , то есть тоже степенью двойки противоречие с тем, что в рассматриваемом случае . Следовательно, при любом N , отличном от степени двойки, раскладка не может быть собрана в одну кучку.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Объединяя оба случая и , получаем доказательство более общего утверждения: раскладка N камней может быть собрана в одной кучке тогда и только тогда, когда количество камней в каждой её кучке делится на набольший нечётный делитель N .

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

Заметим, что при обоих разрешённых действиях дробь не уменьшается и всегда остается меньше единицы.

Действительно, от второго действия величина дроби не меняется, осталось проверить первое действие.

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

просто перемножим крест-накрест, получив

что равносильно

Последнее неравенство очевидно следует из .

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

Давайте проверим сумму всех чисел. Была: , стала: . То есть сумма является полуинвариантом и всегда уменьшается на , а значит, когда-то она станет отрицательной, но тогда хотя бы одно из чисел отрицательно, что нам и требовалось доказать.

Мысль: Видишь задачу с процессом? Перебери самые популярные инварианты и полуинварианты: четность, сумма, произведение, площадь, периметр, делимость.