|
|
 |
Условие
У Ани и Бори было по длинной полосе бумаги.
На одной из них была написана буква А, на другой – Б. Каждую минуту один
из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе
слово с полосы другого. Докажите, что через сутки слово с Аниной полосы
можно будет разрезать на 2 части и переставить их местами так, что
получится то же слово, записанное в обратном порядке.
Решение
Назовем палиндромом слово, читающееся одинаково
справа налево и слева направо.
Докажем индукцией по n , что через n минут слово на
любой полоске можно будет разрезать на два палиндрома (один из которых,
возможно, пустой). Тогда, если эти палиндромы переставить местами,
получится то же слово, записанное в обратном порядке.
При n = 0 или 1 это, очевидно, верно. Пусть n>1 . Без ограничения общности
можно считать, что на первом ходу Боря приписал к своему слову А слева,
т.е. после первого хода написаны слова А и АБ. Посадим Антона и Валю в
этот момент за полоски, на которых написаны буквы А и В, и попросим их
повторять действия Ани и Бори (т.е. если Аня приписывает к началу Борино
слово, то Антон приписывает Валино, и т.п.). Получившийся процесс длится
n - 1 минуту. Тогда в конце процесса слова Антона и Вали можно разрезать
на два палиндрома каждое, а если в них заменить каждую букву В на
последовательность АБ, то получатся слова Ани и Бори.
Докажем, что если к палиндрому из букв А и В приписать в конце А и
заменить каждую букву В на АБ, то получится палиндром. Действительно,
пусть перед первой В стояло x0 букв А, между первой и второй – x1 ,
после последней, k -й буквы В – xk букв А. Тогда
xi=xk+1-i при любом 1 i
k . В измененном слове перед
первой буквой Б будет x0+1 букв А, между первой и второй – x1+1 ,
после последней, k -й буквы Б – xk+1 букв А. Поскольку
xi+1=xk+1-i+1 , то полученное слово также будет палиндромом.
Пусть, скажем, Антоново слово из букв А и В
разрезается на палиндромы S и
T . Пусть S' и T' – слова, полученные заменой В
на АБ.
Если слово T' непусто, то S' А
и T' А – палиндромы, слово T' начинается с А
( T'А=АT'' А), и поэтому T'' – тоже
палиндром. Тогда
Анино слово разрезается на палиндромы S' А и T'' .
Если же слово T' пусто, то S'=АS'' ( S''
– палиндром)
является требуемым разбиением. Доказательство для
Бориного слова
аналогично.
