Слова с ограничениями

32

Слова с ограничениями

А. М. Степин,
А. Т. Таци-Заде

Эта статья по теме очень близка к статье Г. А. Гуревича «Бесповторные последовательности», которая была опубликована в «Кванте» № 9 за этот год. Статья посвящена вычисленному количеству (и доказательству существования) слов любой длины (в том числе, и бесконечной), в данном алфавите с ограничениями, — попутно в ней решается задача M300 из «Заданияка «Кванта», № 12, 1974. У Гуревича же вычислилось количество (и доказывалось существование) последовательностей любой длины (и бесконечной), у которых никакая группа цифр не встречается два раза подряд, и решалась задача M310.

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

Наше знакомство со словами и с алфавитами мы научем с разбора задачи M300, предлагавшейся в «Заданиеке «Кванта», см. «Квант» № 12 за 1974 год.

Задание M300

Алфавит состоит из трех букв a, b, c. Назовем словом последовательность любой длины, состоящую из этих букв. При обработании слов некоторых буквосочетания (длины два и более) считаются запрещенными. Известно, что в списке запрещенных буквосочетаний все слова имеют разную длину.

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

Задание M300 можно придать иную — «развлекательную» — форму:

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

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

Решать задачу M300 все же удобно в терминологии «букв» и «слов».

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

Обозначим число хороших слов длины l через $G_l$. Чтобы доказать существование хороших слов любой длины, достаточно показать, что при любом натуральном l число $G_l$ больше нуля. Мы же сейчас показем, что для любого l хороших слов длины l довольно много: $G_l \geq 2^l$.

33

Упорядочим отмещенные слова по длине и обозначим через $l_i$ длину $i$-го отмещенного слова ($l_i \geq i$).

Лемма 1. Для чисел $G_l$ справедливо неравенство

$$G_l \geq 3 \cdot G_{l-1} - \sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{l-l_i} \cdot i$$

($G_1$, оценидно, равно тем; положим $G_0$ равным единице).

Доказательство. Заметим, что все хорошие слова длины $l$ содержатся среди слов, получающихся приписыванием справа одной из букв $a, b, c$ к хорошим словам длины $l-1$. При таком приписывании получается $3 \cdot G_{l-1}$ слов, среди которых, помимо хороших слов, могут быть и неокоторые плоские слова длины $l$. Оценим их число. Очевидно, что в полученном плоском слова отмещенное слово может находиться только в его конце, то есть оно устроено так: последнее $l_i$ букв образуют отмещенное слово, а первый $l-l_i$ букв — хорошое слово ($2 \leqslant l_i \leqslant l$). Число плоских слов (длины $l$) описанного типа, оканичивающих отмещенным словом длины $l_i$, не больше числа хороших слов длины $l-l_i$, то есть числа $G_{l-l_i}$ (по условию у нас есть только одно отмещенное слова длины $l_i$). Все же в результате приписывания справа одной из букв $a, b, c$ к хорошим словам длины $l-1$ получится не более $\sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{l-l_i}$ плоских слов. Значит, среди полученных $3 \cdot G_{l-1}$ слов длины $l$ хороших слов не меньше $3 \cdot G_{l-1} - \sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{l-l_i}$.

*) Сумма $\sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{l-l_i}$ — это, вообще говоря, не то же самое, что $\sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{l-i}$: в первой сумме произвольная суммированные лишь по таким значениями $l_i$, $2 \leqslant l_i \leqslant l$, для которых в списке запретов есть отмещенное слово соответствующей длины $l_i$ (то есть, $l_i$ принимает, быть может, не все из значений 2, 3, …, $l$): так, если в списке запретов нет отмещенного слова длины 3, то в сумме $\sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{l-l_i}$ член $G_{l-3}$ отсутствует.

Неравенство (1) сыгает главную роль при оценке числа $G_l$.

Лемма 2. Для любого натурального $l'$

$$G_l \geq 2 G_{l-1}.$$

(2)

Доказательство леммы 2 проведем метод математической индукции.

База идукции: $l = 1$; очевидно, что $G_1 \geq 2 \cdot G_0$.

Шаг индукции: Предположим, что неравенство (2) выполняено для всех натуральных $l \leqslant L$, то есть

$$\begin{cases} G_L \geq 2 \cdot G_{L-1}, \\ G_{L-1} \geq 2 \cdot G_{L-2}, \\ \dots \\ G_2 \geq 2 \cdot G_1. \end{cases}$$

(2')

Докажем, что $G_{L+1} \geq 2 \cdot G_L$.

Из неравенств (2’) имеем:

$$G_L \geq 2 \cdot G_{L-1} \geq 2^2 \cdot G_{L-2} \geq \dots \geq 2^k \cdot G_{L-k},$$

то есть

$$G_{L-k} \leq G_L/2^k,$$

(2’')

где $k = 1, 2, \dots, L$.

Учитывая оценки (2’’), неравенство (1) и способку к нему, получим, что

$$G_{L+1} \geq 3 \cdot G_L - \sum_{i=1}^{2 \leqslant l_i \leqslant l} G_{L+1-l_i} \geq$$

$$\geq 3 \cdot G_L - \sum_{k=1}^{l} G_{L-k} \geq *$$

$$\geq 3 \cdot G_L - G_L \cdot \sum_{k=1}^{l} \frac{1}{2^k} \geq$$

$$\geq G_L \cdot (3-1) = 2 \cdot G_L,$$

а это и требовалось доказать.

Поскольку $G_{l-1} \geq 2 \cdot G_{l-2}, G_{l-2} \geq 2 G_{l-3}, \dots, G_1 \geq 2 \cdot G_0 = 2$, то $G_l \geq 2^l$, и мы получаем теорему 1:

Для любого натурального $l$ в числовии задачи М300 число хороших слов длины $l$ не меньше, чем $2^l$:

$$G_l \geq 2^l,$$

(3)

которой и заканчивается решение нашей задачи.

*) Здесь уже объявная сумма:

$$\sum_{k=1}^{l} G_{L-k} = G_{L-1} + G_{L-2} + \dots + G_{L-l}.$$

34

Бесконечные слова

Тепер мы знаем, что в «словаре» задачи М300 есть хорошее слова любой длины. А есть ли в нем бесконечное длиные хорошие слова?

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

Возьем самое длиное отчечное слова (так как по предположению число отчечных слов конечно, это можно сделать); пусть еголина равна $n$. Выберем натуральное $N$ так, чтобы $N$ было больше $n$. Поскольку у нас есть хорошее слова любой длины, возьем хорошее слова длины

*) Доказательство этого факта вы можете найти в статье Г. А. Гуревича «Бесповторные последовательности» (см. «Квант» № 9). В статье Гуревича фактически доказано, что из свойства «ессть как угодно длиное хорошее слова» следует свойство «ессть и.beсконечно длиное хорошее слова», то есть что в действительности существование хороших слов любой длины эквивалентно существования.beсконечного длиного хорошего слова. Мы же докажем, что в наших предложениях существует перiodическое.beсконечное слова, и указываем способ, позволяющий такое слово построить (дадим, как принято говорить, конструкторное доказательство).

$N \cdot (3^N + 1)$, обозначим его через $A$. Разделим слова $A$ на $(3^N + 1)$ равных по длине частей $B_k$ длины $N$: если

$$A = x_1, x_2, \dots, x_N \cdot (3^N + 1).$$

где $x_i$ — это $a$, либо $b$, либо $c$, то $B_k = x_N \cdot (k - 1) + 1, x_N \cdot (k - 1) + 2, \dots, x_N \cdot k.$

Поскольку $A$ — хорошее слова, каждое $B_k$ — тоже хорошее слова длины $N$. Но в нашем алфавите всего три буквы $(a, b, c)$, поэтому различных хороших слов длины $N$ будет не более, чем $3^N$. У нас же получилось $(3^N + 1)$ хороших слов $B_k$; значит, среди них есть одинаковые. Пусть, например, $B_{n_1} = B_{n_2}$ и $n_1 < n_2$. Возьем кусок слова $A$, состоящий из частей $B_k$ с номерами $k$ от $n_1$ до $n_2 - 1$ включительно. Это будет хорошее слова $C$ длины $m \geq N$:

$$C = x_N \cdot (n_1 - 1) + 1, \dots, x_N \cdot (n_2 - 1).$$

Припишем к слову $C$ справа то же самое слова $C$. Получим слова $D$ длины $2m$:

$$D = x_N \cdot (n_1 - 1) + 1, \dots, x_N \cdot (n_2 - 1),$$

$$x_N \cdot (n_1 - 1) + 1, \dots, x_N \cdot (n_2 - 1).$$

Доказем, что $D$ — хорошее слова.

Предположим противное: $D = CC$ — плоское слово; тогда оно содержит какое-то отчечное слово. Очевидно, что это отчечное слово

35

может нахождение только в области «склейки» двух хороших слов $C$, так что его пересечение с «правым» и «левым» словами $C$ не пусто. Но $B_{n_1} = B_{n_2}$ илина любого отмеченного слова меняше $N$; значит, это отмеченное слово должно лежать в области «склейки» частей $B_{n_2}-1$ и $B_{n_1}$ хорошого слова $A$, а этого не может быть, и, следовательно, слово $D$ — хорошое.

Понятно, что бесконечное переодическое слово $CC \dots C$ с перiodом $C$ будет также хорошим, а это, собственно, и дает все, что нужно.

Итак, наш автоматический может разъездать по городу бесконечного долго, не нарушая при этом правил уличного движения!

Интересный пример

Вернемся к неравенству (1), с доказательствам которого мы начали решение задачи М300; перепишем его так:

$$G_l - 3 \cdot G_{l-1} + \sum_{l_i, 2 \leqslant l_i \leqslant l} G_{l-l_i} \geqslant 0.$$ (4)

Насколько точно это неравенство? Можно ли в нем знак «≥» заменить знаком «=»? Вообше говоря, нельзя, и вот почему.

Число $3 \cdot G_{l-1}$ — это число слов, получившихся приписыванием справа к хорошим словам длины $l-1$ одной из букв $a, b, c$; среди таких слов находятся все хорошие слова длины $l$. Вычитая из числа $3 \cdot G_{l-1}$ числа $G_{l-l_i}$, где $l_i$ — какое-то из значений 2, 3, …, $l$ (возможно, и все значения), мы тем самым как бы вычеркиваем из построенных слов длины $l$ все те плоские слова, которые получаются, если к хорошему слову длины $l-l_i$ добавить отмеченное слово длины $l_i$. Но при этом может получиться так, что какое-то плоское слово длины $l$ оказывается вычеркинутым несколько раз из числа $3 \cdot G_{l-1}$ получившихся слов. Если же среди наших $3 \cdot G_{l-1}$ слов длины $l$ нет слов, получающихся из хороших слов длины $l-l_i$ приписыванием справа отмечного слова длины $l_i$, то соответственно число $G_{l-l_i}$ вообше вычитать не надо.

Однако при некоторых дополнительных условиях на список запретов вместе рекуррентных нераевенств (4) для чисел $G_l$ ($l$ — любое) будут выполятаться аналогичные рекуррентные равенства:

$$G_l - 3 \cdot G_{l-1} + \sum_{l_i, 2 \leqslant l_i \leqslant l} G_{l-l_i} = 0.$$ (4')

В таких случаях $G_l$ записьвается явно в виде функции от $l$, и для каждой конкретного значения $l$ число $G_l$ можно посчитать.

В частности, из сказанного следует, что для справедливости рекуррентных равенств (4’) достаточно таких двух условий:

1. Среди слов длины $l$, получающихся приписыванием справа одной из букв $a, b, c$ к хорошим словам длины $l-1$, находящего все слова, получающихся из хороших слов длины $l-l_i$ приписыванием справа отмечного слова длины $l_i$ (оно по предположению есть в списке запретов).

2. Каждый полученное максимum приписыванием (одной буквы) положое слово длины $l$ представляет в виде какого-то хорошого слова (меньшей длины) и отмечного слова единственный образом.

Условие 2° выполняется, если в списке запретов никакое отмечное слово не является концом какого-нибудь другого отмечного слова.

Уражение 1. Проверить, что для алфавита из трех букв и списка отмечных слов $ab, acb, accb, \dots, ac\dots cb$ выполняется условия 1° и 2°, и что для чисел $G_l$ справедливый также рекуррентные соотношения:

$$G_l - 3 \cdot G_{l-1} + G_{l-2} + \dots + G_{l-s} = 0.$$ (5)

(s — длина самого длиного отмечного слова).

Если списк запретов упражнения 1 ограничить двумя отмечными словами $ab$

*) Уравнение вида $G_l + b_1 G_{l-1} + b_2 G_{l-2} + \dots + b_s G_{l-s} = 0$ ($b_1, \dots, b_s$ — некоторые постоянные), называются конечно-разностными уравнениями; о методах их решения можно прочесть в книге А. О. Гельфона «Исчисление конечных разностей». М., «Наука», Глава V, § 4, п. 2.

36

и acb, то мы получим уравнение
$$G_l - 3 \cdot G_{l-1} + G_{l-2} + G_{l-3} = 0. \quad (5')$$
Решение уравнения (5’) будем искать в виде
$$G_l = \lambda^l. \quad (5'')$$
Подставляя (5’’) в (5’), получим уравнение
$$\lambda^3 - 3\lambda^2 + \lambda + 1 = 0,$$
имеющие три различных корня:
$$\lambda_1 = 1, \quad \lambda_2 = 1 + \sqrt{2}, \quad \lambda_3 = 1 - \sqrt{2}.$$
Общее решение уравнения (5’) записывается так:
$$G_l = C_1 + C_2 (1 + \sqrt{2})^l + C_3 (1 - \sqrt{2})^l,$$
где $C_1, C_2$ и $C_3$ — постоянные, определенные из начальных условий:
$$G_0 = 1, \quad G_1 = 3, \quad G_2 = 8.$$
Получается такая система для определения $C_1, C_2, C_3$:
$$\begin{cases} C_1 + C_2 + C_3 = 1, \\ C_1 + C_2 (1 + \sqrt{2}) + C_3 (1 - \sqrt{2}) = 3, \\ C_1 + C_2 (3 + 2\sqrt{2}) + C_3 (3 - 2\sqrt{2}) = 8, \end{cases}$$из которого находится
$$C_1 = -\frac{1}{2}, \quad C_2 = \frac{3}{4} + \frac{\sqrt{2}}{2}, \\ C_3 = \frac{3}{4} - \frac{\sqrt{2}}{2},$$
значит,
$$G_l = -\frac{1}{2} + \left(\frac{3}{4} + \frac{\sqrt{2}}{2}\right) \cdot (1 + \sqrt{2})^l + \left(\frac{3}{4} - \frac{\sqrt{2}}{2}\right) \cdot (1 - \sqrt{2})^l$$
(в частисти, $G_3 = 20$).

Обобщение задачи М300

Пусть менярь алфавит состоящим из $n$ буква $a_1, a_2, \dots, a_n$, а в списке отмещенных слов (длины не меньше двух) имеется более $m$ различных слов одинаковой длины.

Сейчас мы докажем, что при некоторых ограничениях начища $n$ и $m$ и в таком «слове» будут сколь угодно длиные хорошие слова, причем для каждой натурального $l$ ($l$ — длина слова) — опять-tаки довольного многого.

Как и при решении задачи М300 (для М300 имеем: $n=3, m=1$) вначале нужно докажать.

Лемму 3. При выполнении условий «обобщенной задачи М300» для чисел $G_l$ хорошо схов длины $l$ верны также соотношение:
$$G_l \geq n \cdot G_{l-1} - \sum_{i=1}^{n-1} m_i \cdot G_{l-i}, \quad (6)$$
еде через $m_i$ обозначено число отмещенных слов длины $l_i$ ($G_1$, оченьindo, равно $n$, а $G_0$ снова полагаем равным 1).

Лемма 3 доказывается в точности теми же рассужdenями, что и лемма 1 (см. с. 33); мы ее доказываем не будем.

Так как по условияю каждой $m_i$ не больше $m$ (в дальнейшем мы будем считать $m = \max\{m_i\}$ и называть $m$ кратностью системы ограничений), то
$$G_l \geq n \cdot G_{l-1} - m \cdot \sum_{i=1}^{n-1} G_{l-i}. \quad (7)$$
Следующий после леммы 3 шаг — доказательство важной леммы 4:
$$m \leq \left(\frac{n-1}{2}\right)^2, \quad (8)$$
мо. существует макое $\lambda > 1$, что для любого натурального $l$
$$G_{l+1} \geq \lambda \cdot G_l. \quad (9)$$
Лемма 4, как и лемма 2 первого параграфа, доказывается методом математической индукции с использованием неравенства (7) и соответствий (2’) и (2’’), в которых число «2» заменяется буквой «λ» (см. с. 33). Индикционный переход от $L$ к $L+1$ возможно, поскольку квадратное относительное $\lambda$ неравенство
$$n - \frac{m}{\lambda - 1} \geq \lambda$$ с неотрицательным (в силу (8)) дискриминантом
$$\left[ \left(\frac{n-1}{2}\right)^2 - m \right]$$ имеет решение
$$\lambda_1, 2 = \frac{n+1}{2} \pm \sqrt{\left(\frac{n-1}{2}\right)^2 - m}.$$
Так как $G_1 = n \cdot G_0$ (напомним, что $G_0 = 1$) и
$$n \geq \frac{n+1}{2} + \sqrt{\left(\frac{n-1}{2}\right)^2 - m},$$
то
$$G_1 \geq \left(\frac{n+1}{2} + \sqrt{\left(\frac{n-1}{2}\right)^2 - m}\right) \cdot G_0,$$
и существует числа $\lambda > 1$ доказано.
Наконец, аналогично теореме 1, мы пслучим теорему 2:
Если в условия «обобщенной задачи М300» $m \leq \left(\frac{n-1}{2}\right)^2$, то

Блокирующие ограничения

А нужно ли вообще ограничение (8) на кратность системы запретов?

Мы уже видели, что условие $m \leqslant \left(\frac{n-1}{2}\right)^2$ достаточно для существования сколь угодно длинного хорошего слова. Это условие нельзя, вообще говоря, ослабить. В самом деле, при $n = 2$ для алфавита из двух букв $a$ и $b$ получаем условие на кратность $m \leqslant \frac{1}{4}$. Положим $m = 1$ и возьмем в качестве отмеченных такие три слова:

$$ab,\ aaa,\ bbbb.$$

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

Д о к а з а т е л ь с т в о (от противного).

Предположим, что существует хорошее слово длины 6. Оно кончается буквой $a$, или буквой $b$.

Если это слово кончается буквой $b$, то поскольку сочетание $ab$ запрещено, то наше «хорошее» слово состоит только из букв $b$, чего не может быть, так как сочетание $bbbb$ запрещено.

Пусть это хорошее слово (длины 6) кончается буковой $a$; рассмотрим его предпоследнюю букву: — если она $b$, то и все остальные буквы (5 штук) должны быть $b$ — а этого не должно быть. Значит, наше слово оканчивается на $aa$. Возьмем теперь третью от конца букву нашего слова: если это опять $a$, то сказывается запрет $aaa$, если же это $b$ — то остальные буквы (4 штуки) — тоже $b$, и сказывается запрет $bbbb$.

Приведем еще один пример блокирующей системы запретов — для алфавита из трех букв $a$, $b$, $c$. Для такого алфавита условие (8) нам дает, что $m$ должно быть не больше 1. Положив $m = 2$, т. е. предположив, что можно отмечать по два слова одинаковой длины, возьмем в качестве отмеченных следующие слова:

$$ab,\ ac;\ bcb,\ bcc;\ aaaa,\ bbbb;\ ccccc.$$

У п р а ж н е н и е 2. Докажите, что эти отмеченные слова образуют блокирующее ограничение на хорошие слова.

Какую максимальную длину в этом случае имеет хорошее слово?

Из рассмотренных для $n = 2$ и 3 примеров следует, что существует блокирующая система запретов с кратностью $m$, такой, что

$$\left(\frac{n-1}{2}\right)^2 < m \leqslant \left(\frac{n-1}{2}\right)^2 + 1.$$

Но для произвольного натурального $n$ и целого $m$, где

$$\left(\frac{n-1}{2}\right)^2 < m \leqslant \left(\frac{n-1}{2}\right)^2 + 1,$$

существование бокирующей системы запретов для алфавита из $n$ букв с кратностью $m$ не доказано. Докажем, что для алфавита из $n$ букв $a_1,\ \ldots,\ a_n$ блокирующая система запретов с кратностью $m = \frac{n\,(n-1)}{2}$ существует. Действительно, возьмем такую систему запретов

(1) $a_1a_2$, (2) $a_1a_3$, . . . , $(n-1)\ a_1a_n$,

$(n)\ a_2a_3$, . . . , $\left(\frac{n\,(n-1)}{2}\right) a_{n-1}a_n$.

Тогда хороших слов длины больше $2n$ не будет, а единственным хорошим словом длины $2n$ будет слово

$$a_na_na_{n-1}a_{n-1}\ldots a_1a_1.$$

Но, конечно, в каждом конкретном случае все зависит от того, как устроена система запретов. Достаточно, например, для алфавита из двух букв $a$, $b$ $(n = 2)$ и $m = 1$ взять в качестве отмеченных слова

$$aa,\ aba,\ abaa,\ abaab,\ \ldots,$$

как мы получим, что существует даже бесконечно длинное, периодическое слово $bb\ldots b\ldots$ . Более того, можно взять $m$ равным даже четырем (и уж конечно — двум и трем), а в качестве отмеченных, например, слова:

$$aa,\ ab,\ ba,\ aab,\ aba,\ baa,\ aaa,$$

и мы снова получим бесконечное хорошее слово $bb\ldots b\ldots$ .

В заключение мы предлагаем читателям, заинтересовавшимся «проблемой хороших слов», порешать задачи.

1. Докажите, что для алфавита $a$, $b$ не существует системы блокирующих ограничений, состоящей меньше чем из трех слов.

2. Докажите, что в случае $n = 3$ и $m = 2$ не существует бокирующей системы меньше чем из шести отмеченных слов.

3. Докажите, что если для алфавита $a$, $b$, $c$ отмечены слова $ca$, $cb$, $ba$, то $G_l$ растет как $l^2$.

4. Докажите, что $G_{l_1+l_2} \leqslant G_{l_1} \cdot G_{l_2}$.

5. Докажите, что для алфавита из $n$ букв существует блокирующая система ограничений с кратностью $m$, такой, что

$$\frac{n\,(n-2)}{2} + 2 \leqslant m < \frac{n\,(n-2)}{2} + 3.$$

37