Задача 109776

Темы:    [ Процессы и операции ] [ Теория алгоритмов (прочее) ] [ Индукция (прочее) ]

Сложность: 5+ Классы: 8,9,10,11

Условие

Автор: Черепанов Е.

У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква А, на другой – Б. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 2 части и переставить их местами так, что получится то же слово, записанное в обратном порядке.

Решение

Назовем палиндромом слово, читающееся одинаково справа налево и слева направо.
Докажем индукцией по 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'' – палиндром) является требуемым разбиением. Доказательство для Бориного слова аналогично.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2003
Этап
Вариант	5
Класс
Класс	11
задача
Номер	03.5.11.4