Инвариант

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

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

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

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

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

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

Цель первого игрока — добиться появления на доске фишки с весом 1 (т. е. фишки в первой клетке). Когда фишка сдвигается из клетки в клетку ее вес удваивается.

Игра в терминах весов выглядит следующим образом:

1.

Первый игрок разделяет множество всех фишек с общим весом на два подмножества с весами и где

2.

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

Докажем критерий выигрыша в обе стороны.

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

______________________________________________________________________________________________________________________________________________________

Лемма. Любое мультимножество фишек с весами из набора

и суммарным весом можно разбить на два подмножества, вес каждого из которых не менее

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Случай 2: Докажем, что в этом случае выигрывает второй игрок.

Стратегия второго игрока: после того как первый разделит фишки на группы и выбирать ту, у которой вес меньше. Пусть Тогда так как

Второй игрок оставляет группу и новый вес становится

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

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

Пусть — число в клетке в конечный момент времени.

Рассмотрим в качестве инварианта взвешенную сумму всех чисел на доске

где — текущее число в клетке.

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

Если ход совершается с вертикальными соседями и изменение суммы будет:

Аналогично, если от числа отнимается 2, а к соседям прибавляется по 1, изменение суммы также будет равно нулю. Таким образом, величина является инвариантом.

Теперь сравним значения инварианта в начале и в конце. В начальный момент времени поэтому:

В конечный момент времени поэтому:

Поскольку — инвариант, откуда следует ключевое равенство:

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

Теперь рассмотрим сумму квадратов разностей между начальной и конечной конфигурациями:

Используя равенства и получаем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда

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

Первое решение. Докажем, что для любой пары записанной на доске, число делится на

Действительно, для пары число делится на 7.

Пусть для пары число делится на Тогда для пары число

делится на и для пары число

делится на

Пусть для пар числа делятся на 7. Тогда для пары число

делится на

Так как для пары число

не делится на эта пара на доске появиться не может.

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

Утверждение. Докажем, что все тройки, появляющиеся на доске, имеют вид

с целыми и В начальный момент времени это верно:

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

Утверждение доказано.

_________________________________________________________________________________________________________________________________________________________________________________

Предположим теперь, что на доске появилась тройка (2022, 2023, -4045), то есть она имеет вид Тогда имеем

Выражая из первого равенства и подставляя во второе, получаем

то есть

Однако это невозможно, поскольку не делится на

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

Действительно, пусть для некоторой операции выбран кусок, в котором по букв A и B, причём из этих букв A стоят на нечётных местах. Тогда на чётных местах в куске стоят букв A и, следовательно, букв B. После операции именно из этих букв B возникнут буквы A, стоящие на нечётных местах куска — значит, количество таких букв A не поменяется.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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