Олимпиадная задача по математике на периодичность слов из букв "A" и "B" для 7-9 классов
Задача
Рассматривается последовательность слов из букв "A" и "B". Первое слово – "A", второе – "B". k-е слово получается приписыванием к (k–2)-му слову справа (k–1)-го (так что начало последовательности имеет вид: "A", "B", "AB", "BAB", "ABBAB", ...). Может ли в последовательности встретиться "периодическое" слово, то есть слово, состоящее из нескольких (по меньшей мере двух) одинаковых кусков, идущих друг за другом, и только из них?
Решение
Легко видеть, что в k-е слово входят ровно Fk–2 букв А и ровно Fk–1 букв В (k ≥ 3, Fk – числа Фибоначчи). Если бы это слово было периодическим, то и Fk–1, и Fk–2 делились бы на число вхождений периода. Но соседние числа Фибоначчи взаимно просты (см. зад. 160573).
Ответ
Не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь