Задача 97970

Темы:    [ Рекуррентные соотношения (прочее) ] [ Периодичность и непериодичность ] [ НОД и НОК. Взаимная простота ] [ Доказательство от противного ] [ Числа Фибоначчи ]

Сложность: 4 Классы: 7,8,9

Условие

Рассматривается последовательность слов из букв "A" и "B". Первое слово – "A", второе – "B". k-е слово получается приписыванием к (k–2)-му слову справа (k–1)-го (так что начало последовательности имеет вид:  "A", "B", "AB", "BAB", "ABBAB", ...).  Может ли в последовательности встретиться "периодическое" слово, то есть слово, состоящее из нескольких (по меньшей мере двух) одинаковых кусков, идущих друг за другом, и только из них?

Решение

Легко видеть, что в k-е слово входят ровно F_k–2 букв А и ровно F_k–1 букв В  (k ≥ 3,  F_k – числа Фибоначчи). Если бы это слово было периодическим, то и F_k–1, и F_k–2 делились бы на число вхождений периода. Но соседние числа Фибоначчи взаимно просты (см. зад. 60573).

Ответ

Не может.

Замечания

1. Ср. с задачей 97976.

2. 8 баллов.

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

олимпиада
Название	Турнир городов
Турнир
Номер	9
Дата	1987/1988
вариант
Вариант	весенний тур, основной вариант, 7-8 класс
Задача
Номер	7