Олимпиадная задача о лентах Ани и Бори: перестановка и обращение слова (8–11 класс)

Назовем палиндромом слово, читающееся одинаково справа налево и слева направо. Докажем индукцией по n , что через n минут слово на любой полоске можно будет разрезать на два палиндрома (один из которых, возможно, пустой). Тогда, если эти палиндромы переставить местами, получится то же слово, записанное в обратном порядке.

При n = 0 или 1это, очевидно, верно. Пусть n>1. Без ограничения общности можно считать, что на первом ходу Боря приписал к своему слову А слева, т.е. после первого хода написаны слова А и АБ. Посадим Антона и Валю в этот момент за полоски, на которых написаны буквы А и В, и попросим их повторять действия Ани и Бори (т.е. если Аня приписывает к началу Борино слово, то Антон приписывает Валино, и т.п.). Получившийся процесс длится n - 1минуту. Тогда в конце процесса слова Антона и Вали можно разрезать на два палиндрома каждое, а если в них заменить каждую букву В на последовательность АБ, то получатся слова Ани и Бори.

Докажем, что если к палиндрому из букв А и В приписать в конце А и заменить каждую букву В на АБ, то получится палиндром. Действительно, пусть перед первой В стояло x₀ букв А, между первой и второй – x₁ , после последней, k -й буквы В – x_k букв А. Тогда x_i=x_k+1-i при любом1 i k . В измененном слове перед первой буквой Б будет x₀+1букв А, между первой и второй – x₁+1, после последней, k -й буквы Б – x_k+1букв А. Поскольку x_i+1=x_k+1-i+1, то полученное слово также будет палиндромом.

Пусть, скажем, Антоново слово из букв А и В разрезается на палиндромы S и T . Пусть S' и T' – слова, полученные заменой В на АБ. Если слово T' непусто, то S' А и T' А – палиндромы, слово T' начинается с А ( T'А=АT'' А), и поэтому T'' – тоже палиндром. Тогда Анино слово разрезается на палиндромы S' А и T'' . Если же слово T' пусто, то S'=АS'' ( S'' – палиндром) является требуемым разбиением. Доказательство для Бориного слова аналогично.

Ответ задачи отсутствует