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

Заметим, что сумма исходных чисел - нечетное число. Когда мы  к любым двум из них одновременно добавляем по единицы, тем самым к сумме мы добавляем число 2, и сумма остается нечетной. Это и есть инвариант для данного преобразования:  четность суммы чисел не меняется при одновременном добавлением единицы к двум любым числам. То есть сколько раз мы бы не добавляли единицы, четность суммы не изменится.

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

Пронумеруем места фишек.   Обозначим фишки, стоящие на нечетных местам красным цветом, а стоящие на четных - желтым. Заметим, что если мы меняем местами фишки, стоящие через одну, то не меняется четность места, на которых они стоят:

Это и есть инвариант для данного преобразования: четность места, на котором стоит фишка сохраняется. То есть если изначально фишка стояла на четном месте, то в результате любого числа таких перестановок она останется на четном месте.

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

Поскольку по условию задачи одновременных решений не было, то есть девочки решали задачи последовательно, следовательно, в результате решения каждой задачи девочки получали суммарно 4+2+1=7 конфет. То есть в результате решения всех задач девочки суммарно должны получить  число конфет, кратное семи. Если девочки говорят, что что каждая из них решила все задачи и получила 20 конфет, то суммарно они получили 60 конфет. Что невозможно.

Если в условии число 20 поменять на 21, то получим суммарное число конфет, кратное 7. Но это еще не гарантия того, что такая ситуация возможна. Чтобы доказать, что ситуация возможна, нужно привести пример.

Если девочки получили одинаковое число конфет, значит, каждая из них одинаковое число раз решила задачу первой, второй и третьей:

Если эта ситуация повторится трижды, то каждая девочка получит по 21 конфете.

В каждой горизонтали и в каждой вертикали шахматной доски по 4 белых и 4 черных клетки. Всего на шахматной доске 32 белых и  32 черных клетки.

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

Возьмем доску размером 7х7. Предположим, мы смогли получить единственную черную клетку. Возьмем квадрат 2х2 клетки, содержащий эту черную клетку:

Мы должны были получить эту конфигурацию из исходной конфигурации для шахматной доски:

       такой:                                                       или такой:

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

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

5. На доске написано число 12. В течение каждой минуты число либо умножают, либо делят на 2 или на 3, и результат записывают на доску вместо исходного числа. Докажите, что число, которое будет написано на доске ровно через час, не может быть равно 54.

Решение.

Разложим числа 12 и 54 на простые множители.

Заметим, что если мы сложим показатели степеней в разложении числа 12, то получим число 3. При делении или умножении на 3 или на 2 сумма показателей увеличивается или уменьшается на 1, то есть при каждом таком действии меняется четность суммы показателей. Через час, то есть через 60 мин совершится 60 изменений четности суммы показателей, то есть четность суммы показателей не изменится и в результате этих действий она останется нечетным числом.

Сумма показателей степеней в разложении числа 54 равна 4,  это четное число.

То есть ни при каком четном числе умножений или делений на 2 или 3 мы не можем из числа 12 получить число 54.

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

Заметим, что в каждом случае остатки от деления на 3 числа хамелеонов каждого цвета  - это числа 0; 1; 2. И это инвариант данных преобразований.

Всего у нас 45 хамелеонов. Если все хамелеоны станут одного цвета, то остатки от деления чисел 0;0 и 45 на 3 будут равны нулю. А эта ситуация ни при каком числе встреч хамелеонов произойти не может.

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

Но , а число 10 не кратно трем. Поэтому получить многочлен мы не можем.

Если бы мы каждый раз вместо любых двух чисел и писали их сумму  , то в результате мы получили бы сумму всех исходных чисел. Причем не важно в каком порядке мы их складываем - от перемены мест слагаемых сумма не меняется. Но мы записываем не сумму двух чисел, а выражение , то есть в результате каждой операции мы вычитаем 1. После 19 таких операций мы сложим все числа, и из полученной суммы вычтем 19.

По Формуле для суммы членов арифметической прогрессии получаем ответ:

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

Легко проверить, что сумма чисел 1+2+...+2013 - это число нечетное.

Нужно помнить, что для любых чисел и их сумма и разность имеют одинаковую четность. Действительно, . - четное число, и если к любому числу прибавить четное число, то его четность исходного числа не изменится. То есть если мы имеем сумму нескольких слагаемых, то при изменении любых знаков "+" на "-" четность результата не изменится.

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

Пусть на доске записаны числа и . Среднее арифметическое чисел , ,... равно

.

То есть среднее арифметическое чисел и равно

Среднее гармоническое чисел , ,... есть число, обратное среднему арифметическому чисел, обратных числам , ,...:

Среднее гармоническое чисел и равно .

Если мы среднее арифметическое чисел и умножим на их среднее гармоническое, то для любых и получим

То есть для любых и произведение их среднего арифметического и среднего гармонического равно произведению этих чисел: . Следовательно, в результате всех замен, которые Петя производил над исходными числами 1 и 2, остается постоянным произведение полученных чисел, равное .

Следовательно, если одно из полученных чисел равно 941664/665857, то второе будет равно

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

То есть . Если город С совпадает с городом А, то есть из города В он отправится в город А, это означает, что расстояние от города В до А - наибольшее, и путешественник вернется в А, а затем опять отправится в В и будет перемещаться между этими двумя городами.

Если город С не совпадает с городом А, следовательно, он отправится в город С, и будет отправляться в следующий город до тех пор, пока расстояние от предпоследнего города до последнего не будет самым большим по сравнению с расстоянием от последнего города до любого другого. И тогда путешественник начнет перемещаться туда-сюда между последним и предпоследним городом, то есть никогда не попадет в город А.

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

Пусть часть новобранцев повернулись направо, а часть налево:

Пусть сержант в каком-то месте встанет в строй, и пусть число смотрящих на него слева (сержант смотрит на нас) меньше, чем тех, кто смотрит на него справа:

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

Либо число тех, кто смотрел на него слева не изменится, а число тех, кто смотрел на него справа увеличится на 1:

В любом случае разница в числе тех, кто изначально смотрел на сержанта слева и тех, кто смотрел справа уменьшается на 1.

Крайние положения сержанта таковы:

или

В первом случае число тех, кто смотрит на сержанта больше числа тех, кто повернут к нему спиной, то есть разность Л-С>0, а во втором - наоборот, то есть разность Л-С<0. При движении сержанта вправо эта разность, как мы выяснили, уменьшается на 1, следовательно, в какой-то момент она станет равной нулю, и тогда число новобранцев, смотрящих на сержанта справа и слева будет одинаковым.