Инвариант

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что:

Введём инвариант:

Каждая операция сохраняет значение После всех операций останется одна пара чисел и причём:

Отсюда получается, что пункт доказан. Также заметим, что:

Тогда введем аналогичный инвариант:

Он также не изменяется при любых операциях, тогда для оставшихся в конце чисел верно:

Тогда

Тем самым пункты и доказаны.

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

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

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

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

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

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

Посмотрим, что происходит с периметром всей клетчатой фигуры, заросшей бурьяном. Когда новая клетка заполняется бурьяном, она имеет хотя бы две заросшие соседние клетки, а значит, хотя бы две ее стороны уже до ее заполнения посчитаны в общем периметре всей фигуры. Тогда после ее заполнения она сможет добавить в периметр не более двух новых сторон (то есть увеличить не более, чем на 2), но все ее стороны, которыми она примыкает к соседним заросшим клеткам, ”удалятся“ из периметра, то есть больше не будут на границе фигуры. Значит, периметр уменьшится хотя бы на 2. Итого, периметр не может увеличиться после одной операции.

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

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

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

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

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

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

Пусть определяют по слову языка альфов количество в нём букв А и Л соответственно. Заметим, что все операции не меняют значения величины по модулю Действительно, порядок букв на это свойство не влияет. Остальные же операции либо просто не меняют эту разность (ЛА ФФ, ФФ ЛА), либо изменяют ровно на (АФ ЛЛ, ФЛ АА, ЛЛ АФ, АА ФЛ). Но тогда значение должно совпадать по модулю для двух рассмотренных слов. Для ЛЛАФАЛАФФАЛАФФФАЛАФФФФАЛЛ оно равно а для ЛФАЛФАЛФАЛФАЛАФЛАФЛАФЛАФЛ равняется Эти числа не равны по модулю