|
|
 |
Условие
Володя решил стать великим писателем. Для этого он каждой букве русского языка сопоставил слово, содержащее эту букву. Потом написал слово, сопоставленное букве "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 баллов
