ГЛАВНАЯ » РЕШЕБНИК

2019-01-19   
Существует ли бесконечная периодическая последовательность, состоящая из букв $а$ и $b$, такая, что при одновременной замене всех букв $а$ на $aba$ и букв $b$ на $bba$ она переходит в себя (возможно, со сдвигом)? (Последовательность называется периодической, если существует такое натуральное $n$, что для всякого $i = 1, 2,\cdots$ $i$-й член этой последовательности равен $(i + n)$-му).


Решение:


Натуральное число $n$ назовем периодом периодической последовательности $x_1x_2\cdots$, если $x_i = x_{i+n}$ для всех $i = 1,2,\cdots$ Легко доказать, что

1) любой период кратен наименьшему;

2) для любого к наименьшие периоды последовательностей $x_1x_2\cdots$ и $x_{k+i}x_{k+2}\cdots$ совпадают.
Пусть $x_1x_2\cdots$ - последовательность, удовлетворяющая условиям задачи и $n$ - ее наименьший период.

Рассмотрим три случая: $n = 3m, n = 3m + 1, n = 3m - 1$ (1).

Пусть $n = 3m$. Число $m$ не является периодом последовательности ($m < n$), поэтому найдется пара $x_i, x_{i+m}$ такая, что $x_i \neq x_{i+m}$. Заменив все буквы $x_i, \cdots, x_{i+m}$ по правилу $a \rightarrow aba, b \rightarrow bba$, мы получим фрагмент последовательности:

$x_iba \underbrace{ \ast \ast \cdots\ast }_{3m-3}x_{i+m}ba$.

Но, согласно сделанным замечаниям, из того, что $n = 3m$, следует, что начальная тройка букв этого фрагмента совпадает с конечной. Получили противоречие.

Пусть $n = 3m + 1$. Тогда, как и выше, найдется пара $x_i \neq x_{i+m}$. Но тогда вторая буква фрагмента (1) должна совпадать с последней, что не так. Аналогично, если $n = 3m - 1$, то третья буква фрагмента (1) должна совпадать с предпоследней. Противоречие.
Ответ. Не существует.