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

Проект МЦНМО
при участии
школы 57
Задача 109885
Темы:    [ Периодичность и непериодичность ]
[ НОД и НОК. Взаимная простота ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Существует ли такая бесконечная периодическая последовательность, состоящая из букв a и b, что при одновременной замене всех букв a на aba и букв b на bba она переходит в себя (возможно, со сдвигом)?


Решение

  Натуральное число n назовём периодом периодической последовательности x1x2..., если xi = xi+n для всех  i = 1, 2, ... . Легко доказать, что
    любой период кратен наименьшему;
    для любого k наименьшие периоды последовательностей x1x2... и xk+1xk+2... совпадают.
  Пусть x1x2... – последовательность, удовлетворяющая условиям задачи, и n – её наименьший период. Рассмотрим три случая.
  1)  n = 3m.  Число m не является периодом последовательности  (m < n),  поэтому найдётся такая пара xi, xi+m, что  xi ≠ xi+m.  Заменив все буквы xi, ..., xi+m по правилу  aaba,  b → bba,  мы получим фрагмент последовательности:       (1)
  Но, согласно сделанным замечаниям, из того, что  n = 3m,  следует, что начальная тройка букв этого фрагмента совпадает с конечной. Противоречие.
  2)  n = 3m + 1.  Тогда, как и выше, найдётся пара xi ≠ xi+m.  Но тогда вторая буква фрагмента (1) должна совпадать с последней, что не так.
  3)  n = 3m – 1.  Тогда третья буква фрагмента (1) должна совпадать с предпоследней. Противоречие.


Ответ

Не существует.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1996
Этап
Вариант 4
Класс
Класс 11
задача
Номер 96.4.11.8

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

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