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

Проект МЦНМО
при участии
школы 57
Задача 97970
Темы:    [ Рекуррентные соотношения (прочее) ]
[ Периодичность и непериодичность ]
[ НОД и НОК. Взаимная простота ]
[ Доказательство от противного ]
[ Числа Фибоначчи ]
Сложность: 4
Классы: 7,8,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 делились бы на число вхождений периода. Но соседние числа Фибоначчи взаимно просты (см. зад. 60573).


Ответ

Не может.

Замечания

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

2. 8 баллов.

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

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

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

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