Инвариант

(a) Докажем, что данный процесс не может продолжаться бесконечно. Пусть в начале на полосе лежат камней. За каждый ход общее количество камней уменьшается на следовательно общее количество ходов не превосходит то есть конечно.

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

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

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

(b) Аналогично предыдущему пункту покажем, что процесс не может продолжаться бесконечно. Пусть камень, лежащий в клетке с номером имеет вес (число Фибоначчи). Тогда операция не меняет сумму весов, а финале получится запись исходной суммы весов в фибоначчиевой системе счисления.

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

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

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

Для каждой клетки () на диагонали квадрата (то самой, на которой стояли знаки «») построим домик — четверку клеток (), (), (), (); все индексы здесь считаются вычетами по модулю Заметим, что домики разных клеток не пересекаются: в столбце находятся клетки () и () из домика () и (), () из домика (); другие домики на этот столбец не залезают.

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

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

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

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

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

т.к. Значит, при наших операциях эта сумма не меняется.

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

т.к. все числа попарно различны по условию. Значит, мы не можем получить искомую расстановку.

Заметим, что и , и делятся на . Поэтому любая сумма, которую мы можем ими набрать, также будет делиться на . Но число на не делится, значит, набрать его этими монетами нельзя.

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

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

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

Посмотрим, как меняется общее число камней. При использовании заклинания “Добавляйтус” количество камней увеличивается на и уменьшается на , значит, в итоге увеличивается на . При использовании заклинания “Забирайтус” количество камней уменьшается на и на , то есть в итоге уменьшается на . Числа и делятся на , как и изначальное количество камней . Поэтому у Рона общее число камней всегда будет делиться на . С другой стороны, спрашивается, может ли стать камней . Так как это число на не делится, то добиться указанного числа камней в кучах не получится.

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

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

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

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

Обратим внимание, что изначально количество лягушек во всех кучах делится на . Покажем, что это свойство сохранится. Когда мы делим пополам кучу, в которой количество камней было четным и делилось на , мы получим две кучи, в которых также количество камней делится на . Когда мы объединяем две кучи, причем в обеих количество камней делилось на , то и суммарное число камней в новой куче будет делиться на . Значит, ни при каком действии свойство “количество камней во всех кучах делится на ” не пропадает. Поэтому и в конце это свойство будет выполняться. С другой стороны, так как всего лягушек , а ребят трое, то при делении всех лягушек на три равные кучи должно получить три кучи по лягушек. Но число не делится на , значит, добиться такого количества лягушек в кучах не удастся.

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

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

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

Решение 2: Посмотрим на четность разности количества букв «О» и «М» в слове. Так как в буквосочетаниях «МО» и «OOMM» количество букв «О» и «М» равное, то при их добавлении или исключении из слова, разность количества букв «О» и «М» в слове не меняется. Осталось заметить, что в словах «ММО» и «ОММО» эта разность равна 1 и 0 соответственно, значит, данные слова не синонимы.

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

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