Поиск инварианта

32

Ю. Ионин, Л. Курляндчик

Понск
инварианта

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

Задача 1. На доске написано десять плосков и пятнадцать минутсов. Разрешается стеремь любые два знака и написать вместе их плоск, если они одинаковы, и минутс в противном случае. Какой знак останется на доске после выполнения двадцатим минутов операций?

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

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

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

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

Проанализируем все три решения.

Первое решение основывает на неизменемости произведения написанных чисел, второе — на неизменемости четности их суммы и третье — на неизменемости четности числа минутсов. В математике вместе с слова «неизменяемость» употребляют термин «инвариантность». Можно сказать, что в каждом решении нам удалось найти инвариант: произведение написанных чисел, четность суммы, четность числа минутсов. Решение последующих задачи и упражнения также основывается на удачном подборе инварианта.

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

Задача 2. В таблице 4×4 знаки «+» и «—» рассматриваются как показано на рисунке 1. Разрешается изменить знак на промивоположный одновременно во всех клетках, расположенных в одной строке, в одном столбце или вдоль прямой, параллельной какой-нибудь из диагоналей (в частности, в любой угловой клетке). Можно ли с помощью этих операций получить таблицу, не содержащую ни одного минута?

Решение. Заменим плоскы и минутсы чисlami 1 и —1. В качестве инварианта можно взять произведение чисел, находящихся в клетках, которые

33

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

Упражнение 2. Решите задачу 2 для таблицы, изображенных на рисунках 3—5.

Задача 3*). На доске написано несколько нулей, единиц и двоеек. Разрешается стеремь две неравные чисцы и вместе их написать одну цифру, отличную от стеремых (2 вместо 0 и 1, 1 вместо 0 и 2, 0 вместо 1 и 2).
Докажите, что если в результате нескольких таких операций на доске останется одна-единственная цифра, то она не зависит от порядка, в котором произвольись стерема.

*) Это — задача М338 из «Задачника «Кванта», см. «Квант», 1975, № 8.

Рис. 1.
Рис. 2.
Рис. 3.

Решение. Обозначим через $x_0, x_1, x_2$ число нулей, единиц и двоеек соответственно. Выполнить один раз разрешенную операцию, мы изменим каждое из этих чисел на 1 и, следовательно, изменим четность всех трех чисел. Когда на доске остается одна цифра, два из чисел $x_0, x_1, x_2$ становится равным нулю, а третье — единица. Значит, с самого начала два из этих чисел имеют одну четность, а третье — другую. Поэтому независяимо от того, в каком порядке произвольятся стеремя, в конце едините может равнять лишь одно из чисел $x_0, x_1, x_2$, которое с самого начала не ту четность, что два других.

Из приведенного решения видно, что если числа $x_0, x_1, x_2$ имеют одну и ту же четность, то мы не сможем добиться, чтобы на доске осталась одна-единственная цифра. Докажите, что если чисел $x_0, x_1, x_2$ есть как чётные, так и нечётные, и, кроме того, хотя бы два из них отличны от нуля, то существует такой порядок

Рис. 4.
Рис. 5.
Рис. 6.

34

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

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

Рассужждение с четырьмя здесь не помогает, но в результате выполнения каждой операции одно из чисел $x_0, x_1, x_2$ меняет свою четность, а два других сохраняют четность, так что числа, имеющие разную четность, могут теперь получить одну и ту же четность. Однако можно заметить, что остатки от деления чисел $x_0, x_1, x_2$ на 3 изменяются каждый раз таким образом, что равные остатки остаются равными, а нервные остаются нервными. Дальнейшие расчужнения повторяют решение задачи 3.

Задача 4. В каждой клетке таблицы $8 \times 8$ написано некоторое целое число. Разрешается выбрать в таблице любой квадрат размерами $3 \times 3$ или $4 \times 4$ и увеличивать на единицу все стоянные клетках выбранного квадрата числа. Всегда ли можно с помощью таких операций преобразовать исходную таблицу в таблицу, у которой числа делятся на 3?

Решение и.e. Нет, не всегда. Найдем сумму чисел, написанных в заштрихованных на рисунке 6 клетках. Поскольку любой квадрат размерами $4 \times 4$ содержит 12 заштрихованных клеток, а квадрат размерами $3 \times 3$ — 6 или 9 таких клеток, то в результате описанной операции остаток от деления на 3 этой суммы (чисел, стоящих в заштрихованных клетках) не будет меняться. Поэтому, если с самого начала найденная сумма не делится на 3, то среди заштрихованных клеток все время будут сохраняться клетки, в которых написанные числа не кратны тем.

У разженние 3. Из всякой ли таблицы можно в условиях задачи 4 получить таблицу, не содержащую четных чисел?

Задача 5. Числа 1, 2, 3, …, $n$ расположены в некотором порядке. Разрешается менять местами любые два рядом стоянных числа. Доказите, что если проделать нечетное число таких операций, то наверняка получится отличное от первогоначального расположение чисел 1, 2, 3, …, $n$.

Решение. Пусть $a_1, a_2, ..., a_n$ — произвольная перестановка из чисел 1, 2, 3, …, $n$. Будем говорить, что числа $a_i$ и $a_j$ образуют в этой перестановке инверсии, если $i < j$, но $a_i > a_j$, то есть большее из этих чисел предшествует меньшему. Поменяв местами два соседних числа в перестановке, мы увеличим или уменьшим число инверсии на 1. Проделав же нечетное число таких операций, мы изменим четность числа инверсии, а значит, изменим и перестановку.

У разженние 4. Доказите, что утверждение задачи 5 остается справедливым, если разрешить местами любые два числа в перестановке.

У казан и.e. Доказите, что любые два числа можно поменять местами, проделав нечетное число операцию, описанной в задаче 5.

Переход от одной перестановки чисел 1, 2, 3, …, $n$ к другой перестановке этих чисел, при котором какие-либо два числа меняются местами, а остальные остаются на месте, называется транспозицией. Результат упражнения 4 можно сформировать так: выполнить нечетное число транспозиции, мы изменим перестановку.

Задача 6. В различных пунктах количество автоматом в одной и то же время в одном направлении стармовали 25 автоматом. По правилам автоматом могут обойти друг друга, но при этом запрещен двойной обойти. Автомобили филишировали одновременно в тех же пунктах, что и стармовали. Доказите, что во времяzonки было четное число обознавов.

Решение. Окраим один из автоматов в желтый цвет, а остальные автоматом присвоит номера

35

1, 2, 3, …, 24 в том порядке, в каком они располагаются на старте за желтым автоматом. В центре авторома установлен свойство табли, на котором после каждого обгона будем указать номера автоматей в том порядке, в каком они следует за желтым автоматом. Тогда обгон, в котором не участвует желтый автоматиль, приводит к тому, что на световом табло меняются местами два соседних числа.

Постотрим, что произойдет, если какой-нибудь автоматиль обгонит желтый. Если перед этим обгоном числа на табли образовывали перестановку $a_1, a_2, a_3, ..., a_{24}$, то после обгона они образуют перестановку $a_2, a_3, ..., a_{24}, a_1$. Заметим, что к такой же перестановке можно прийти, выполив последовательное 23 трансозиции:

$$a_1, a_2, a_3, ..., a_{24} \rightarrow a_2, a_1, a_3, ..., a_{24}, a_1.$$

Если же желтый автоматиль совершил обгон, то из перестановки $a_1, a_2, a_3, ..., a_{24}$ мы получим перестановку $a_{24}, a_1, a_2, a_3, ..., a_{24}, a_1.$

Этот переход также можно заменить два соседних числа трансозиции.

Таким образом, либо обгон сводится к нечетному числу трансозиции. Если бы общее число обгонов было нечетным, то нечетным оказалось бы и общее число трансозиции. Остается воспользоваться результатом управления 4.

Уражнения
5. По окружности выписаны в произвольном порядке четыре единиц и пять нуля. В промежуток между двумя одинаковыми цифрами выписается 1, а между разными 0, после чего все первоначальные цифры стираются. Можно ли, повторив несколько раз эту операцию, получить набор из девятей нуля?
6. Петь разорвал листок бумаги на десять кусков, неоторые из этих кусков он снова разорвал на десять части, и т. д. Мог ли Петь получить таким путем 1975 кусочков бумаги?
7. На доске написаны числа 1, 2, 3, …, 1975. Разрешается стереть любые два числа

и написать вместе стертых чисел остatok от деления суммы этих чисел на 13. После некоторого числа таких операций на доске осталось одно число. Каким оно может быть?

8. Каждый от 1 до 1 000 000 заменяет числом, равным сумме его цифр. С получившимся числам продаваяют ту же операцию, и так делают до тех пор, пока числа не станут однозначными. Каких чисел в результате получения большие: единиц или двое?
9. Из трехначного числа вычису его цифр. С получившимся числом продаваяют то же самое, и так далее — это раз. Какое в результате получения число?
10. Круг разбит на 10 секторов, в каждом из которых стоит по одной цифре. Одним ходом разрешается любые две фишки передвинуть в соседние секторы, но так, чтобы фишки двигались при этом в противоположных направлениях. Можно ли собрать все фишки в одном секторе?
    11a). В верхне $A_{12}$ правильно 12-угольника $A_1A_2A_3...A_{12}$ поставлен минус, а в остальных вершинах — плоцы. Разрешается выбрать любые три вершины, образующие непрямуюный равноведенный треугольник, и изменить знаки, написанные в этих вершинах, на противоположные. Можно ли с помощью таких операций добиться, чтобы в верхне $A_1$ оказался минус, а в остальных вершинах — плоцы?
    6). Сохранить ли результат управления a), если допустить перемену знака в верхних любого равноведенного треугольника, в том числе и прямогоного? *).
11. В каждой клетке таблицы $4 \times 4$ написан плоскус. Разрешается одновременно менять знак на противоположный во всех клетках одной строки или одного столца. Наименьшее число минус, к которой можно прийти, начав с данной таблицы, называется характерисмкой этой таблицы. Какие значения может принять характерисмкой?
12. По кругу стоит 30 фишек — 10 белых и 20 черных. Разрешается менять местами любые две фишки, между которых стоит еще три фишки. Два расположения фишек называются эквивалентными, если одно из них можно получить из другого, применив несколько раз указанного операцию. Сколько существует неэквивалентных расположений фишек?
13. Числа 1,2,3, …, 1975 записаны по порядку. Разрешается выбрать любые числа и расставить их на тех местах, которые они занимали, но в обратном порядке. Можно ли с помощью таких операций прийти к расположению 1975, 1974, …, 3, 2, 1?

*) Эту задачу прислал в «Квант» ученик 10 класса школь № 3 г. Нахивана Вилаям Гусейов.