|
|
 |
Условие
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.
Решение
Рассмотрим последовательность слов:Докажем методом полной индукции следующее утверждение: в n-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых n букв алфавита, то такие подслова появятся. Тогда 33-е слово является требуемым (в русском алфавите 33 буквы).
База индукции. Для n = 1 утверждение очевидно.
Шаг индукции. Пусть утверждение справедливо для всех слов с номерами от 1 до n - 1. Рассмотрим n-е слово. В нем n-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с (n - 1)-м словом.
Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в (n - 1)-м слове. Значит, одно из них содержит n-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в n-м слове тоже нет соседних одинаковых подслов.
Если приписать к n-му слову n-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером k < n, то k-е слово, которое является началом и концом n-го слова, даст два соседних одинаковых подслова (по предположению индукции).
Комментарии. 1o. Длина искомого 33-го слова равна 233 - 1, что составляет примерно 10 миллиардов букв!
2o. Построенные слова играют важную роль в комбинаторике и теории полугрупп. Определим последовательность слов Zn равенствами: Z1 = x1; Zn + 1 = Znxn + 1Zn, где xi - переменные (вместо которых можно подставлять слова). Попытайтесь доказать, что при любом n в любой бесконечной последовательности букв конечного алфавита встретится слово вида Zn, где вместо x1, ..., xn подставлены некоторые слова. Например, встретится слово вида x1x2x1, где x1, x2 - слова.
