Закл до 2015

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

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

Докажем, что если к палиндрому из букв и приписать в конце и заменить каждую букву на то получится палиндром. Действительно, пусть перед первой стоит букв между первой и второй — после последней, -й буквы — букв Тогда при любом В измененном слове перед первой буквой будет букв между первой и второй — после последней, -й буквы — букв Поскольку то полученное слово также будет палиндромом.

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