Применение классических комбинаторных методов к разным задачам → .07 Инвариант

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

Первое решение. Назовём дискриминантом пары чисел величину

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

Далее, верны следующие соотношения:

и

поэтому на доске ни в какой момент не может появиться пара с положительным дискриминантом. Теперь рассмотрим любую выписанную на доску пару В ней первое число

______________________________________________________________________________________________________________________________________________________

Второе решение. Если на доске написана пара то с помощью первой операции можно добавить пары

Обе этим пары можно записать как

где в первом случае а во втором — С помощью второй операции можно добавить только пару

______________________________________________________________________________________________________________________________________________________

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

Для пары утверждение задачи верно. Далее, рассмотрим два типа операций:

Тогда для новой пары верно

Здесь также получаем нужное неравенство:

______________________________________________________________________________________________________________________________________________________

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

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

Пример. Рассмотрим все слов, у которых начиная с -ой все буквы Ш, а первые — У или Я. Этот набор слов удовлетворяет условию.

Оценка. Каждому из наших слов сопоставим слов, заменяя каждую букву Ш, на У или Я (всеми возможными способами). Заметим, что полученные слов состоят из букв У и Я и попарно различны (для слов, полученных из одного и того же, это ясно из построения, а для слов, полученных из двух разных, следует из условия). Таким образом, и

______________________________________________________________________________________________________________________________________________________

Замечание. Оценку можно получить по-другому.

Способ 1. Подкинем монетку раз. Для каждого слова рассмотрим такое событие: при всяком если на некоторой позиции стоит буква У, то при -м подбрасывании выпала решка, а если буква Я, то орёл. Вероятность такого события равна и они не совместные, поэтому количество слов не больше чем

Способ 2. Пусть выбрано более слов. Присвоим каждому слову вес Пусть первая буква у слов У, у слов — Я и Удвоим веса всех слов с первой буквой У, и обнулим — с первой буквой Я. Далее посмотрим на вторую букву и т.д. Опишем шаг рассмотрения -ой буквы. Пусть — сумма весов слов, у которых -ая буква У, — сумма весов слов, у которых -ая буква Я. Если удваиваем веса у слов с -й буквой Я и обнуляем — с -й буквой У. Иначе — наоборот. В результате таких операций сумма весов не уменьшается. После операций сумма весов всех слов будет больше В каждом слове только букв У или Я, поэтому вес каждого слова не больше Значит, найдутся два слова с одинаковыми весами. Тогда для них не найдется позиции, в которой у одного У, а у другого Я или наоборот, противоречие.

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

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

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

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

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

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

Значит, мы хотим сравнить два произведения: и . Сделаем это:

Понятно, что равенство не выполнено. Значит, инвариант не сохраняется, так что из тройки получить тройку нельзя.

Пример. Расставим сначала фишки на все чётные места, кроме -го (рядом по пустых), а затем — на все нечётные, кроме -го (рядом по пустых).

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

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

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

Пример. Пример при котором получается

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

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

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

С другой стороны,

что противоречит неравенству выше.

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

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

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

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

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

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

Заметим, что произведение после применения операций равно Действительно, в начале произведение равно После применения первой операции оно равно так как два числа были стерты, а вместо них было написано

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

Всего до того, как останется одно число, сделано шагов, поэтому в конце будет

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

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

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

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

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

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