Инварианты

19

Иnvariants

В «Кванте» уже писалось о решении задачи при помощи подбора инварианта (1976, № 2, с. 32). В данной статье обсуждаются понятие инварианта и ряд возможных в связи с ним вопросов.

1. Общая постановка задачи

При помощи инвариантов решаются задачи следующого типа: данные множества $M$ (элементы его мы будем называть «позициями») и правила, по которым разретается переходим от одной позиции к другой; можно ли из данной позиции $\alpha$ перейти за несколько шагов в другую данную позицию $\beta$? Более общая задача: как для произвольной пары позиций $\alpha$, $\beta$ устанавливаем, можно ли из $\alpha$ за несколько шагов перейти в $\beta$?

Очевидно, описанные ситуации обладают следующим свойством: если из позиции $\alpha$ можно перейти в позицию $\beta$ и из $\beta$ можно перейти в позицию $\gamma$, то из $\alpha$ можно перейти в $\gamma$. Это свойство называется трансиминностью.

Рассмотрим конкретную задачу.

Задача 1. Круе разделен на секторов, в которых как-то рассматриваны $n$ фишек. Разретается одновременно перевинуть любые две фишки: одну — на один сектор по часовий стрелке, другую — на один сектор в промивоположном направлении. Можно ли из позиции $\mu$, в котором в каждой секторе стойдит по одной фишке, перейти из позиции $\alpha$ в любую другую позицию, принадлежую той же

*) «Кванте», 1972, № 2, c. 2.

21

Дело в том, что если $f$ — инвариант, то из $f(\alpha) = f(\beta)$, вообще говоря, ничего не вытекает. Если $f(\alpha) \neq f(\beta)$, то позиции $\alpha$ и $\beta$ не эквивалентны (это следует из (1)). Если же $f(\alpha) = f(\beta)$, то позиции $\alpha$ и $\beta$ могут быть как эквивалентными, так и не эквивалентными: инвариант не запрещается на разных орбитах приимать одинаковые значения. (Например, постоянная функция, т. е. функция, которая на всех элемах из $M$ принимает одно и то же значение, тоже инвариантна.)

Как же быть? Попробуйте для каждого-nибудь $n$ вида 4 $k$ перейти от позиции $\mu$ к позиции $v$… Почем-то не удается. Попробуем найти другой, более тонкий инвариант.

Занутерум секторы (скажем, по часовой стрелке) от 1 до $n$. Для произвольной расстановки $\alpha$ физек по секторам обозначим через $a_k(\alpha)$ количество физек в $k$-м секторе при расстановке $\alpha$. Расмотрим теперь такую функцию $q$:
$$q(\alpha) = 1 \cdot a_1(\alpha) + 2 \cdot a_2(\alpha) + 3 \cdot a_3(\alpha) + \dots + n \cdot a_n(\alpha).$$

Является ли функция $q$ инвариантом? Произвольное допустимое перемещение (рис. 5) затрагивает 4 слагаемых суммы (2):
$$\dots + i \cdot a_i(\alpha) + (i + 1) \cdot a_{i+1}(\alpha) + \dots + (j - 1) \cdot a_{j-1}(\alpha) + j \cdot a_j(\alpha) + \dots$$

При перемещении, изображенном на рисунке 5, сумма (3) превращается, оченьindo, в сумму
$$\dots + i \cdot [a_i(\alpha) - 1] + (i + 1) \cdot [a_{i+1}(\alpha) + 1] + \dots + (j - 1) \cdot [a_{j-1}(\alpha) + 1] + j \cdot [a_j(\alpha) - 1] + \dots$$

Легко проверяется, что обе суммы равны. Итак, $q$ — инвариант! Нет, мы забили, что $n$-й сектор граничит с первым. Значит, есть еще 3 возможности (рис. 6—8). Подсчет, аналогичный только что сделанному, показывает, что в случае, изображенном на рис. 6, $q(\alpha)$ уменьшится на $n$, а в случае рисунка 7 — увеличится на $n$. В третьем случае $q(\alpha)$, конечно, не изменится. Итак, за одно перемещение значение функции $q$ может измениться, но только на $n$. Следова-

22

Значит, $q(v) = l \cdot n$ и $r(v) = 0$ (каковы бы ни были $n$ и $l$). С другой стороны,
$$a_1(\mu) = a_2(\mu) = \dots = a_n(\mu) = 1.$$
Значит,
$$q(\mu) = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$
Если $n = 2m$, то $q(\mu) = n \cdot m + m$ и $r(\mu) = m \neq 0$. Следовательно, при четном $n$ получаем $r(\mu) \neq r(v)$. Итак, при четном $n$ позиции $\mu$ и $v$ не эквивалентны.
Если же $n = 2m + 1$, то $q(\mu) = n \cdot (m+1)$ и $r(\mu) = 0$. Таким образом, при четном $n$ мы опять имеем: $r(\mu) - r(v)$. Получается, что при четном $n$ вопрос об эквивалентности позиций $\mu$ и $v$ снова остается открытым.

3. Универсальный инварант

Назовем инварант $f$ универсальным, если на неэквивалентных позициях он принимает различные значения:
если $\alpha \neq \beta$, то $f(\alpha) \neq f(\beta)$.
Таким образом, для универсального инваранта $f$
если $f(\alpha) = f(\beta)$, то $\alpha \sim \beta$.
Универсальный инварант на каждой орбите принимает свое значение. Поскольку для универсального инваранта
$$\alpha \sim \beta \iff f(\alpha) = f(\beta),$$
универсальный инварант для любой пары позиций позволяет установить, эквивалентны они или нет.
Как проверить, что неокотый инварант $f$ универсален? Общего метода не существует. Иного может помочь следующее простая теорема.
Если $a)$ существуют такие позиции $\delta_1, \delta_2, \dots, \delta_l$, что каждая позиция $\alpha \in M$ эквивалентна одной из них и $b)$ инварант $f$ принимает, по крайней мере, $l$ различных значений, то $f$ — универсальный инварант и позиции $\delta_i, \delta_j (i \neq j)$ поарно не эквивалентны.
Из $a)$ вытекает, что существует не более $l$ орбит. Из $b)$ вытекает, что существует не менее $l$ орбит. Следовательно, существуетровно $l$ орбит. Снова из $b)$ вытекает теперь, что инварант $f$ принимаетровно $l$ значений и значений, $f$ универсален. Наконее, из $a)$ вытекает, что позиции $\delta_1, \delta_2, \dots, \delta_l$ принимает разным орбитам и, таким образом, попарно не эквивалентны.

Задача 1 (окончание). Докажем, что инварант $r$ универсален. Обозначим через $\delta_i$ такую расстановку физек: одна физка — в $i$-м секторе, все остальные — в $n$-м секторе. Под $\delta_n$ мы будем, разумеется, попарать расстановку, при которой все $n$ физек — в $n$-м секторе.

Легко сообщать, что любая расстановка эквивалентна одной из позиций $\delta_1, \delta_2, \dots, \delta_n$. В самом деле, пусты $a$ — произвольная расстановка физек. Попытемся собрать все $n$ физек в $n$-м секторе. Для этого будем перевратить первый физек, пока не загоним ее в $n$-й сектор; одновременно, в соответствии с правилами, мы будем перемешать вторую физек в противоположную сторону. Затем загоним в $n$-й сектор вторую физек, двигая в противоположную сторону третью физек, и так далее — вплоть до $(n-1)$-й физек. Когда мы загоним $n-1$ физек в $n$-й сектор, $n$-я физка будет в каком-то $i$-м секторе $(i=1, 2, \dots, n)$. Это и означает, что $\alpha \sim \delta_i$.

Посчитаем $r(\delta_i)$. При $i \neq n$:
$$\begin{cases} a_1(\delta_i) = a_2(\delta_i) = \dots = a_{i-1}(\delta_i) = \\ = a_{i+1}(\delta_i) = \dots = a_{n-1}(\delta_i) = 0, \\ a_i(\delta_i) = 1, \\ a_n(\delta_i) = n-1. \end{cases}$$
Следовательно, $q(\delta_i) = i \cdot 1 + n \cdot (n-1)$ и $r(\delta_i) = i$. Кроме того, $q(\delta_n) = n \cdot n$ и $r(\delta_n) = 0$. Итак, инварант $r$ принимает по крайней мере $n$ значений.

По теореме инварант $r$ универсален и позиции $\delta_1, \delta_2, \dots, \delta_n$ попарно не эквивалентны.

Поскольку $r$ — универсальный инварант,
$$\alpha \sim \beta \iff r(\alpha) = r(\beta).$$

24

имеют место одновременного тогда и только тогда, когда позиции α и β эквивалентны.

В чем суть этого определения? Если позиции α и β эквивалентны, то, поскольку $f_1, f_2, \dots, f_k$ — инварианты, каждое из равенств системы (5) все равно выполняется. «В эту сторону» полотна еще ни при чем. Если бы инварианты $f_1, f_2, \dots, f_k$ были универсальными, то эквивалентность позиции α и β вытекала бы из любого равенства системы (5). Нам не дана их универсальное, но затем требуется, чтобы одновременное выполнение системы (5) выклонивалоность позиции α и β. Именно в этом суть поняття полотны. Таким образом, хотя неокоторые из инвариантов $f_1, f_2, \dots, f_k$ могут на неоквивалентных позициях α, β принимать одинаковое значение, значения набора $\langle f_1, f_2, \dots, f_k \rangle$ на них различны.

Полная система инвариантов — это обобщение понятия универсального инварианта: если $f$ — универсальный инвариант, то система $\langle f \rangle$, состоящая из одного инварианта, конечно, полна.

Задача 3. В таблице 2×2 записьюются целые числа. Разрешается, во-первых, в любом стольце одновременное: к одному числу прибавить 2, из другого — вывести 2 и во-вторых, в любой строке одновременное: к одному числу прибавить 3, из другого — вывести 3. Какие таблицы эквивалентны?

Рассмотрим три функции: для любой таблицы

$$\alpha = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$

обозначим через $p(\alpha)$ сумму $a + b + c + d$, через $q(\alpha)$ — остаток от деления числа $a + b$ на 2 и через $r(\alpha)$ — остаток от деления числа $a + c$ на 3. Функции $p, q, r$ являются инвариантами. Не очень трудно доказать, что произвольная таблица α эквивалентна таблице

$$\begin{pmatrix} 0 & q(\alpha) \\ r(\alpha) & p(\alpha) - q(\alpha) - r(\alpha) \end{pmatrix}.$$

Следовательно, из равенств

$$\begin{cases} p(\alpha) = p(\beta), \\ q(\alpha) = q(\beta), \\ r(\alpha) = r(\beta) \end{cases}$$

(6)

вытекает, что таблицы α и β эквивалентны одной и той же таблице и, значит, эквивалентны между собой. И обратно: эквивалентность таблиц α и β является равенства (6), поскольку $p, q$ и $r$ — инварианты. Таким образом, $\langle p, q, r \rangle$ — полная система.

У праванении 8. Решите задачу для таблицы $n \times n$, в которых разрешаются те же преобразования, что и в задаче 3. Естественно ожидать полную систему из 2$n$-1 инвариантов.

У праванении 9. Если $f_1, f_2, \dots, f_k$ — инварианты и $g$ — числовая функция от $k$ аргументов, то функция $h$:

$$h(\alpha) = g(f_1(\alpha), f_2(\alpha), \dots, f_k(\alpha))$$

(7) является инвариантом (ср. с упражением 2). Проверьте.

У праванении 10. Если $h$ — инвариант, а $\langle f_1, f_2, \dots, f_k \rangle$ — полная система инвариантов, то существует также числовая функция $g$ от $k$ аргументов, что выполняется (7) (ср. с упражением 3). Докажите.

У праванении 11. Множество $M$ — множество точек числовой плоскости, то есть множество пар $\langle x, y \rangle$ действительных чисел. Единственный допустимый переход: $\langle x, y \rightarrow \langle y, x \rangle$. Пусть

$$\begin{cases} f_1(x, y) = xy, \\ f_2(x, y) = x + y. \end{cases}$$

Докажать, что $\langle f_1, f_2 \rangle$ — полная система инвариантов.

У праванении 12. Множество $M$ — множество точек пространства или множество треок $\langle x, y, z \rangle$ действительных чисел. Разрешены переходы $\langle x, y, z \rightarrow \langle y, x, z \rangle$ и $\langle x, y, z \rightarrow \langle x, z, y \rangle$. Пусть

$$f_1(x, y, z) = xyz,$$

$$f_2(x, y, z) = xy + yz + zx,$$

$$f_3(x, y, z) = x + y + z.$$

Докажать, что $\langle f_1, f_2, f_3 \rangle$ — полная система инвариантов.

У праванении 13. Множество $M$ состоит из всевозможных наборов (или кортежей) $\langle x_1, x_2, x_3, \dots, x_n \rangle$ действительных чисел (n фиксировано). Разрешается менять местами любые два соседних числа. Найти полную систему инвариантов.