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

Проект МЦНМО
при участии
школы 57
Задача 64586
Темы:    [ Итерации ]
[ Периодичность и непериодичность ]
Сложность: 5
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Володя решил стать великим писателем. Для этого он каждой букве русского языка сопоставил слово, содержащее эту букву. Потом написал слово, сопоставленное букве "A". Дальше каждую букву в нем заменил на сопоставленное ей слово (разделяя слова пробелами), потом в получившемся тексте вновь заменил каждую букву на сопоставленное ей слово, и так всего 40 раз. Володин текст начинается так: "РЯД КОРАБЛЕЙ НА ДРЕМЛЮЩИХ МОРЯХ". Докажите, что этот оборот встречается в Володином тексте еще хотя бы раз.


Решение 1

  Обозначим через Tk текст после k шагов. Заметим, что ни в одном тексте до T40 первая буква не могла на следующем перейти в однобуквенное слово (иначе в дальнейшем первое слово всегда бы оставалось однобуквенным). Значит, каждый раз текст удлинялся хотя бы на одну букву.
  Кроме того, в слове T1 буква А стоит не на первом месте (иначе во всех текстах первое слово начиналось бы на A).
  Поскольку в T1 есть буква A, причём не в начале, то в T2 входит (также не с начала) полученный из этой буквы A текст T1. Аналогично в T3 входит T2, полученный из входящего в T2 текста T1. Но тогда в T3 входит и T1. Продолжая, видим, что в каждом тексте содержатся (не с начала) все предыдущие тексты.
  Пусть Lk – первая буква текста Tk. Последовательность {Lk}, очевидно периодическая (возможно, с предпериодом), причём L34 принадлежит уже второму периоду (в русском языке всего 33 буквы), то есть  L34 = L34–t.  В T34 буква L34 стоит не только на первом месте, но и во входящем в T34 тексте T34–t. Из первой L34 при переходе от T34 к T39 в T39 получатся минимум 6 первых букв, а в T40 – не менее чем 6 первых слов, то есть весь данный в условии фрагмент. Но такой же фрагмент получится из второго вхождения L34 в T34.


Решение 2

  Как показано в решении 1 первая буква любого текста порождает как минимум двухбуквенное слово. Поэтому первая буква L текста T35 порождает минимум пять первых букв в тексте T39, а в тексте T40 – первые пять слов, то есть весь данный в условии фрагмент. Поскольку буква L на первом месте встречалась и раньше, то некоторый текст Tk  (k < 40)  также начинался со слов РЯД КОРАБЛЕЙ НА ДРЕМЛЮЩИХ МОРЯХ. Первые две буквы РЯ этого текста порождают в тексте Т40 весь указанный фрагмент (поскольку буква Я содержится только в последнем его слове). Но Tk содержит и еще один фрагмент РЯ (в слове МОРЯХ), который и порождает в T40 второе вхождение нашего фрагмента.

Замечания

9 баллов

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

олимпиада
Название Турнир городов
Турнир
Номер 29
Дата 2007/2008
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 7

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

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