Олимпиадная задача по индукции и алгебраическим методам для 7–9 классов от Спивак А. В.

Рассмотрим последовательность слов:

Следующее слово получается из предыдущего так: пишется предыдущее слово, затем первая из букв, которых в нем нет, а затем это же слово еще раз. Докажем методом полной индукции следующее утверждение: в n-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых n букв алфавита, то такие подслова появятся. Тогда 33-е слово является требуемым (в русском алфавите 33 буквы).

База индукции. Для n = 1 утверждение очевидно.

Шаг индукции. Пусть утверждение справедливо для всех слов с номерами от 1 до n - 1. Рассмотрим n-е слово. В нем n-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с (n - 1)-м словом.

Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в (n - 1)-м слове. Значит, одно из них содержит n-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в n-м слове тоже нет соседних одинаковых подслов.

Если приписать к n-му слову n-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером k < n, то k-е слово, которое является началом и концом n-го слова, даст два соседних одинаковых подслова (по предположению индукции).

Комментарии. 1^o. Длина искомого 33-го слова равна 2³³ - 1, что составляет примерно 10 миллиардов букв!

2^o. Построенные слова играют важную роль в комбинаторике и теории полугрупп. Определим последовательность слов Z_n равенствами: Z₁ = x₁;

Z_{n + 1} = Z_nx_{n + 1}Z_n, где x_i - переменные (вместо которых можно подставлять слова). Попытайтесь доказать, что при любом n в любой бесконечной последовательности букв конечного алфавита встретится слово вида Z_n, где вместо x₁, ..., x_n подставлены некоторые слова. Например, встретится слово вида x₁x₂x₁, где x₁, x₂ - слова.

Ответ задачи отсутствует