ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 107981
Темы:    [ Индукция (прочее) ]
[ Процессы и операции ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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

Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.


Решение

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

А, АБА, АБАВАБА, АБАВАБАГАБАВАБА, ...

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

Докажем методом полной индукции следующее утверждение: в 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 - слова.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 56
Год 1993
вариант
Класс 8
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .