Бесповторные последовательности

7

Бесповторные последовательности

Г. А. Гуревич

Последовательности Аршона

Назовем последовательность цифр повторной последовательностью, если в ней есть хотя бы одна пара стоянных одинаковых групп цифр. Например, последовательности 1, 2, 3, 4, 2, 3, 4, 2, 1 и 1, 2, 2, 7, 6, 2, 7, 6, 8 — повторные, а последовательности 4, 2, 1, 2, 3, 4, 2, 3 и 3, 2, 3, 1, 2, 7 не являются повторными. Неповторные последовательности мы назовем бесповторными. Через Б(n) обозначим множество последовательностей длины n, а через |Б(n)| — их число.

Интитивно ясно: чем длине последовательность, тем верятнее, что в ней найдется две рядом стоянные одинаковые группы цифр. И в самом деле, если вы научд выпише достаточно длинуную последовательность, то наверняка эта последовательность оказывается повторной.

Придамим этому утверждению точный смысл.

Заддача 1. Докажите, что для любого числа ε > 0 можно указать такое n, что среди всех последовательностей длины n доля бесповторных последовательностей будет меньше ε, то есть $$\frac{|\text{Б}(n)|}{10^n} < \varepsilon.$$

Легко доказать, что все последовательности длины больше трех, составленные из двух цифр 1 и 2 — повторные.

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

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

Обозначим через $K_1$ бесповторную последовательность 1, 2, 3. Предположим, что бесповторная последовательность $K_n$ уже построена. Последовательность $K_{n+1}$ получается из нее так.

Если число $n+1$ четно и на $n+1$-м месте в последовательности $K_n$ стоит 1, то к последовательности $K_n$ приписьвается тройка цифр 3, 2, 1; если стоит 2, — то тройка 1, 3, 2; если стоит 3, — то тройка 2, 1, 3.

Если число $n+1$ нечетно и на $n+1$-м месте в последовательности $K_n$ стоит 1, то к последовательности $K_n$ приписьется тройка 1, 2, 3; если стоит 2, — то тройка 2, 3, 1; если стоит 3, — то тройка 3, 1, 2.

В частиности,

$$K_2 = 1, 2, 3, 1, 3, 2$$
($n = 2$ — число четное, и на втором месте в $K_1$ стоит 2),

$$K_3 = 1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1$$
($n = 3$ — число четное, и на третьем месте в $K_2$ стоит 3),

$$K_4 = 1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1$$
($n = 4$ — число четное, и на четвертом месте в $K_3$ стоит 1) и т. д.

Доказательство бесповторности последовательностей, получающихся по способу Аршона, довольно гро-

8

моздко, и здесь мы его приводить не будем *).

Попробуем теперь оценить число $|B(n)|$ бесповторных последовательностей длины $n$ (из десяти цифр). Если удастся показать, что при любом натуральном $n$ это число больше нуля, то тем самым у нас получится еще одно — уже не конструит вное — доказательство существования сколь угодно длиных бесповторных последовательностей. На самом деле мы сейчас выведем существенно более сильное неравенство $|B(n)| > 8^n$, (1)

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

Задача M310

Тепер вспомним задачу M310 из «Задачника «Кванта» — см. «Квант» № 2 за 1975 год.

Докажите, что среди $n$-значных чисел найдется более $8^n$ максим, в десятичной записи компонных никакая группа цифр (в частности, никакая цифра) не встречается два раза подряд.

Ясно, что решение задачи M310 состоит в доказательстве неравенства (1). Мы докажем сначала неокоторое вспомогательное неравенство, которое пригодится нам в дальнейшем.

Вспомогательное неравенство. Допустим, что выписаны все бесповторные последовательности длины $n$ — всего $|B(n)|$ штук, и мы хотим выписать все бесповторные последовательности длины $n+1$.

Возьемем произвольную последовательность $a_1, a_2, \dots, a_n$ из множества $B(n)$. Запишем новые десять по следующей — длины $n+1$:

$$a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 1, a_1, a_2, \dots, a_n, 9.$$

Так поступим со всеми последовательностями из множества $B(n)$. Получим неокоторое множество последовательностей; обозначим его через $B^*(n+1)$. Среди последовательностей множества $B^*(n+1)$ выберем те, у которых в конце строит две одинаковые цифры. Множество таких последовательностей обозначим через $B_1(n+1)$. Аналогично через $B_2(n+1)$ обозначим множество таких последовательностей из $B^*(n+1)$, у которых в конце два раза подряд строит одна и та же подобледовательность длины $i$. Поскольку все последовательности из $B^*(n+1)$ имеют длину $n+1$, то максимальное $i=n_1$, при котором множество $B_i(n+1)$ не пустое, равно $\left[\frac{n+1}{2}\right]$.

Все последовательности, принадяжшие множества $B_1(n+1), B_2(n+1), \dots, B_{n_1}(n+1)$ — повторные. Докажите самостояльно, что эти mismatches последовательности исчерпываются повторные последовательности множества $B^*(n+1)$ и что множество $B^*(n+1)$ содержит все бесповторные последовательности длины $n+1$.

Позтому, если из множества $B^*(n+1)$ вычеркить все последовательности, принадяжшие множества $B_i(n+1), i=1, 2, \dots, n_1$, то получится множество $B(n+1)$. Следовательно,

$$|B(n+1)| \geq |B^*(n+1)| - |B_1(n+1)| - |B_2(n+1)| - \dots - |B_{n_1}(n+1)|.$$ (2)

9

В силу построения множества $B^* (n+1)$ имеем: $|B^* (n+1)| = 10 \cdot |B(n)|$, и нам нужно только оценить число элементов каждой множества $B_i (n+1)$. Оказывается, $|B_i (n+1)| \leq |B (n+1-i)|$. (3)

Из неравенств (2) и (3) следует важное неравенство, которое мы и называем воспомогательным: $|B (n+1)| > 10 \cdot |B(n)| - (|B(n)| + |B(n-1)| + \dots + |B(1)|)$. (4)

Итак, нам нужно доказать неравенство (3).

Небольшие отсутствие

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

Пусть $A$ — это множество школьников, приведших в книотатр, а $B$ — множество мест в крительном зале. Рассадим школьников по местам. Если остатус свободные места, то $|B| > |A|$. Если все места оказутся занятыми и часть школьников остается без места, то $|A| > |B|$. И наконец, если оказется, что все места заняты и все школьники расскажены, то $|A| = |B|$.

В чем же состоит описанный выше способ? Мы элементам множества $A$ ставили в соответствие элементы множества $B$. Если первыми оказались исчерпанныйми элементы множества $A$, то $|B| \geqslant |A|$, если же — элементы множества $B$, то $|A| \geqslant |B|$. При этом важно то, что разным элементам из $A$ ставились в соответствии разные элементы из $B$ (мы не разрешали одному ученику заниматься сразу места) и, наоборот, разным элементам из $B$ соответствовали разные элементы из $A$ (мы не разрешали каждой на одно место сразу учеников). Такое соответствие называется сdhозначным.

Доказательство неравенства (3)

Попробуем теперь установить однозначное соответствие между множествам $B_i (n+1)$ и частю множества $B (n+1-i)$ ($i=1,2,\dots,n_1$). Напомним, что последовательности из множества $B_i (n+1)$ имеют вид $a_1, a_2, \dots, a_l, b_1, b_2, \dots, b_i, b_1, b_2, \dots, b_{i-1}$ — беспроводная. Значит последовательность $a_1, a_2, \dots, a_l, b_1, b_2, \dots, b_i$ — также беспроводная. Поставим в соответствие последовательности (5) из множества $B_i (n+1)$ последовательность $a_1, a_2, \dots, a_l, b_1, b_2, \dots, b_i$ из множества $B (n+1-i)$:

$a_1, a_2, \dots, a_l, b_1, b_2, \dots, b_i, b_1, b_2, \dots, b_i$

Очевидно, что это соответствие однозначное, причем для каждой последовательности из $B_i (n+1)$ нашлась соответствующая ей последовательность из $B (n+1-i)$. Значит, $|B_i (n+1)| \leqslant |B (n+1-i)|$, и неравенство (3), а значит, и (4), доказаны.

Решение задачи M310

Докажем теперь (индукцией по $n$) еще одно неравенство:

$|B (n+1)| > 8 \cdot |B (n)|$; (6)

10

ясно, что нужно нам неравенство (1) из него следует, поскольку
$$|\beta(n)| > 8 \cdot |\beta(n-1)| > 8^2 \cdot |\beta(n-2)| > \dots > 8^{n-1} \cdot |\beta(1)|,$$
и $|\beta(1)| = 10$.

База индукции. $n = 1$.
$$|\beta(2)| > 8 \cdot |\beta(1)|,$$
так как $|\beta(1)| = 10$, а $|\beta(2)| = 90$.

Индукционный шаг. Предположим, уже доказано, что
$$|\beta(n)| > 8 \cdot |\beta(n-1)|,$$
$$|\beta(n-1)| > 8 \cdot |\beta(n-2)|,$$
$$|\beta(2)| > 8 \cdot |\beta(1)|;$$

нужно доказать неравенство (6).
Из неравенств (7) следует, что
$$|\beta(n)| > 8^i \cdot |\beta(n-i)|,$$
или
$$|\beta(n-i)| < \frac{|\beta(n)|}{8^i},$$
$$i = 1, 2, \dots, n-1.$$

Подставим найденные оценки (7’) для $|\beta(n-i)|$, $i = 1, 2, \dots, (n-1)$, в неравенство (4); получим
$$\beta(n+1)| > 10 \cdot |\beta(n)| - |\beta(n)| \cdot \left(1 + \frac{1}{8} + \dots + \frac{1}{8^{n-1}}\right).$$

Так как
$$1 + \frac{1}{8} + \dots + \frac{1}{8^{n-1}} < 2,$$
то $|\beta(n+1)| > 8 \cdot |\beta(n)|$.

Сформулируем теперь несколько задач.

2. Построите беспроводную последовательность, при приписьвании к концу которой любой цифры всегда будет получаться повторная последовательность.

3. Используя последовательность С. Е. Аршона, доказите существование как углоно длинных последовательностей, составленных из цифр 1 и 2, у которых нет трех одинаковыхрядом стоянных групп цифр.

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

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

Бескочные беспроводные последовательности

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

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

Обозначим через $B$ множество всех конечных беспроводных последовательностей. Поскольку множество $B$ бескочное, а различных цифр — конечное число (всего 10), то найдется по крайней мере одна цифра, с которой начинается бескочное много последовательности из $B$. Обозначим эту цифру через $a_1$. Выбросим из $B$ те последовательности, которые не начинаются с цифры $a_1$. Получим бескочное множество $B^{(1)}$. Аналогично найдется цифра $a_2$, стоящая на втором месте у бескочного числа последовательностей из $B^{(1)}$. Выбросим из $B^{(1)}$ те последовательности, у которых вторая цифра отличается от $a_2$. Получим бескочное множество $B^{(2)}$ и так далее.

Рассмотрим теперь бескочную последовательность $a_1, a_2, \dots$; доказем, что она беспроводная.

Для этого нам достаточно показать, что при любом натуральном $n$ беспроводная конечная последовательность $a_1, a_2, \dots, a_n$. Но по построению все последовательности множества $B^{(n)}$ начинаются с последовательности $a_1, a_2, \dots, a_n$, а множество $B^{(n)}$ является подмножества множества

11

ва Б, и значит, все последовательности из Б^{(n)} бесповторные. Любое же начало бесповторной последовательности само является бесповторной последовательностью.

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

Обобщение

Обозначим буквой P свойство «быть бесповторной последовательностью». Тогда только что доказанное утверждение имеет следующую структуру:

Посылака Следствие

Есть как угодно длинная последовательность, обладающая свойством P

Есть беспонечная последовательность, обладающая свойством P

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

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

1°. Всякое начало последовательности, обладающей свойством P, также обладает этим свойством.

2°. беспонечная последовательность, как угодно длинные начало которого обладает свойством P, также обладает этим свойством.

О пределене. Произвольное свойство числовых последовательностей, удовлетворяющее условием 1°

и 2°, называем наследственным свойством.

Например, свойства «не содержать цифру 3», «состоять только из цифр 1, 2, 3», «начинается цифрой 7» — наследственные свойства, а свойства «содержать беспонечного цифр 4», «кончается цифрой 7» не являются наследственными свойствами.

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

Мы не будем остановываться на доказательстве этой теоремы, поскольку оно полностью повторяет доказательство, приведенное в предыдущем параграфе.

Приложение

Рассмотрим числовые последовательности, составленные из трех цифр: 1, 2, 3. Изовем некоторые последовательности (длины два и более) запрещенными. Известно, что все запрещенные последовательности имеют разную длину.

Изовем последовательности, не содержащие запрещенных последовательностей, правильными.

Обратимся снова к «Задачнику «Квант» — к задачке М300 (см. «Квант» № 12 за 1974 год).

Из утверждения задачи М300 следует, что существуют сколь угодно длинные правильные последовательности. А теперь заметим, что свойство «быть правильной последовательностью» всегда наследеное свойство (доказante!) Значит, утверждение о существовании сколь угодно длинных правильных последовательностей можно заменить более сильным — о существовании беспонечной правильной последовательности, а утверждение задачи М300 — утверждение о существовании беспонечного слова без запрещенных буквосочетаний.