Разделы 
Дополнительно
Задача по математике - 3151
2019-05-26 
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.
Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.
Решение:
Рассмотрим последовательность слов:
А, АБА, АБАВАБА, АБАВАБАГАБАВАБА, $\cdots$.
Следующее слово получается из предыдущего так: пишется предыдущее слово, затем первая из букв, которых в нем нет, а затем это же слово еще раз.
Докажем методом полной индукции следующее утверждение: в $n$-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых $n$ букв алфавита, то такие подслова появятся. Тогда 33-е слово является требуемым (в русском алфавите 33 буквы).
База индукции. Для $n = 1$ утверждение очевидно.
Шаг индукции. Пусть утверждение справедливо для всех слов с номерами от 1 до $n - 1$. Рассмотрим $n$-е слово. В нем $n$-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с ($n - 1$)-м словом.
Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в ($n-1$)-м слове. Значит, одно из них содержит $n$-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в $n$-м слове тоже нет соседних одинаковых подслов.
Если приписать к $n$-му слову $n$-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером $k < n$, то $k$-е слово, которое является началом и концом $n$-го слова, даст два соседних одинаковых подслова (по предположению индукции).
Комментарии.
1. Длина искомого 33-го слова равна $2^{33}-1$, что составляет примерно 10 миллиардов букв!
2. Построенные слова играют важную роль в комбинаторике и теории полугрупп. Определим последовательность слов $Z_n$ равенствами: $Z_1 = x_1; Z_{n+1} = Z_nx_{n+1}Z_n$, где $x_i$ - переменные (вместо которых можно подставлять слова). Попытайтесь доказать, что при любом $n$ в любой бесконечной последовательности букв конечного алфавита встретится слово вида $Z_n$, где вместо $x_1, \cdots, x_n$ подставлены некоторые слова. Например, встретится слово вида $x_1x_2x_1$, где $x_1, x_2$ - слова.
Ответ: Существует.
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.
Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.
Решение:
Рассмотрим последовательность слов:
А, АБА, АБАВАБА, АБАВАБАГАБАВАБА, $\cdots$.
Следующее слово получается из предыдущего так: пишется предыдущее слово, затем первая из букв, которых в нем нет, а затем это же слово еще раз.
Докажем методом полной индукции следующее утверждение: в $n$-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых $n$ букв алфавита, то такие подслова появятся. Тогда 33-е слово является требуемым (в русском алфавите 33 буквы).
База индукции. Для $n = 1$ утверждение очевидно.
Шаг индукции. Пусть утверждение справедливо для всех слов с номерами от 1 до $n - 1$. Рассмотрим $n$-е слово. В нем $n$-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с ($n - 1$)-м словом.
Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в ($n-1$)-м слове. Значит, одно из них содержит $n$-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в $n$-м слове тоже нет соседних одинаковых подслов.
Если приписать к $n$-му слову $n$-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером $k < n$, то $k$-е слово, которое является началом и концом $n$-го слова, даст два соседних одинаковых подслова (по предположению индукции).
Комментарии.
1. Длина искомого 33-го слова равна $2^{33}-1$, что составляет примерно 10 миллиардов букв!
2. Построенные слова играют важную роль в комбинаторике и теории полугрупп. Определим последовательность слов $Z_n$ равенствами: $Z_1 = x_1; Z_{n+1} = Z_nx_{n+1}Z_n$, где $x_i$ - переменные (вместо которых можно подставлять слова). Попытайтесь доказать, что при любом $n$ в любой бесконечной последовательности букв конечного алфавита встретится слово вида $Z_n$, где вместо $x_1, \cdots, x_n$ подставлены некоторые слова. Например, встретится слово вида $x_1x_2x_1$, где $x_1, x_2$ - слова.
Ответ: Существует.
