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

Условие:

Существует ли в русском алфавите конечное слово, в котором нет двух соседних одинаковых подслов, но такие появляются при приписывании произвольной буквы алфавита слева или справа к этому слову? (Поясню подробнее. Слово - произвольный набор букв алфавита, например: ШАЛАШ. Подслово - произвольный набор букв слова, идущих подряд, например: ШАЛ, ЛА, А)

Решение:

Пусть первая буква слова - А. Тогда при приписывании к этому слову слева или справа буквы А будут возникать два идущих подряд одинаковых подслова (А и А).

Давайте будем дальше модифицировать это слово. Если к нему приписать букву Б слева или справа, то сделаем так, чтобы комбинация БА повторилась. То есть теперь исходное слово - АБА.

Затем при приписывании буквы В слева или справа должно возникать повторение комбинации ВАБА, то есть теперь слово - АБАВАБА.

Теперь понятно, каким образом восстановить исходное слово. На следующем шаге будет слово: АБАВАБАГАБАВАБА. И.т.д.

То есть слово можно определить индуктивно: на шаге k, слово будет иметь вид: "слово на шаге (k-1)" "k-я буква алфавита" "слово на шаге (k-1)".

Ответом на задачу будет слово, построенное на 33-м шаге такого алгоритма.

Тогда по построению, как мы видим, оно удовлетворяет второму условию из задачи.

Давайте теперь покажем, что в построенном слове нет двух повторяющихся соседних подслов. Это можно также делать по индукции. В слове АБА нет повторяющихся соседних подслов. Слово на k-м шаге имеет вид: "слово на (k-1) шаге" "k-я буква алфавита" "слово на (k-1) шаге". В слове на (k-1) шаге нет повторяющихся соседних подслов по предположению индукции. Остаётся ещё одна альтернатива - повторяющиеся подслова содержат k-ю букву алфавита. Но в таком случае должно быть по крайней мере две k-х буквы алфавита, что не так (на k-м шаге есть только одна k-я буква алфавита по построению).

Ответ: да, существует.