Разделы 
Дополнительно
Задача по математике - 2005
2019-01-23 
У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква $А$, на другой - $Б$. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 2 части и переставить их местами так, что получится то же слово, записанное в обратном порядке.
Решение:
Назовем палиндромом слово, читающееся одинаково справа налево и слева направо. Докажем индукцией по $n$, что через $n$ минут слово на любой полоске можно будет разрезать на два палиндрома (один из которых, возможно, пустой). Тогда, если эти палиндромы переставить местами, получится то же слово, записанное в обратном порядке.
При $n = 0, 1$ это, очевидно, верно. Пусть $n > 1$. Без ограничения общности можно считать, что на первом ходу Боря приписал к своему слову $А$ слева, т. е. после первого хода написаны слова $А$ и $АБ$. Посадим Антона и Валю в этот момент за полоски, на которых написаны буквы $А$ и $В$, и попросим их повторять действия Ани и Бори (т. е. если Аня приписывает к началу Борино слово, то Антон приписывает Валино, и т. п.). Получившийся процесс длится $n - 1$ минуту. Тогда в конце процесса слова Антона и Вали можно разрезать на два палиндрома каждое, а если в них заменить каждую букву $В$ на последовательность $АБ$, то получатся слова Ани и Бори.
Докажем, что если к палиндрому из букв $А$ и $В$ приписать в конце $А$ и заменить каждую букву $В$ на $АБ$, то получится палиндром. Действительно, пусть перед первой $В$ стояло $х_0$ букв $А$, между первой и второй - $x_i, \cdots$, после последней, $k$-й буквы $В - x_k$ букв $А$. Тогда $x_i = x_{k+1-i}$ при любом $1 \leq i \leq k$. В измененном слове перед первой буквой $Б$ будет $х_0 + 1$ букв $А$, между первой и второй - $x_i + 1, \cdots$, после последней, $k$-й буквы $Б - x_k + 1$ букв $А$. Поскольку $x_i + 1 = x_{k+1-i} + 1$, то полученное слово также будет палиндромом.
Пусть, скажем, Антоново слово из букв $А$ и $В$ разрезается на палиндромы $S$ и $T$. Пусть $S^{\prime}$ и $T^{\prime}$ - слова, полученные заменой $В$ на $АБ$. Если слово $T^{\prime}$ непусто, то $S^{\prime}А$ и $T^{\prime}А$ - палиндромы, слово $T^{\prime}$ начинается с $А (T^{\prime}А = AT^{\prime \prime}А)$, и поэтому $T^{\prime \prime}$ - тоже палиндром. Тогда Анино слово разрезается на палиндромы $S^{\prime}А$ и $T^{\prime \prime}$. Если же слово $T^{\prime}$ пусто, то $S^{\prime} = AS^{\prime \prime} (S^{\prime \prime}$ - палиндром) является требуемым разбиением. Доказательство для Бориного слова аналогично.
У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква $А$, на другой - $Б$. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 2 части и переставить их местами так, что получится то же слово, записанное в обратном порядке.
Решение:
Назовем палиндромом слово, читающееся одинаково справа налево и слева направо. Докажем индукцией по $n$, что через $n$ минут слово на любой полоске можно будет разрезать на два палиндрома (один из которых, возможно, пустой). Тогда, если эти палиндромы переставить местами, получится то же слово, записанное в обратном порядке.
При $n = 0, 1$ это, очевидно, верно. Пусть $n > 1$. Без ограничения общности можно считать, что на первом ходу Боря приписал к своему слову $А$ слева, т. е. после первого хода написаны слова $А$ и $АБ$. Посадим Антона и Валю в этот момент за полоски, на которых написаны буквы $А$ и $В$, и попросим их повторять действия Ани и Бори (т. е. если Аня приписывает к началу Борино слово, то Антон приписывает Валино, и т. п.). Получившийся процесс длится $n - 1$ минуту. Тогда в конце процесса слова Антона и Вали можно разрезать на два палиндрома каждое, а если в них заменить каждую букву $В$ на последовательность $АБ$, то получатся слова Ани и Бори.
Докажем, что если к палиндрому из букв $А$ и $В$ приписать в конце $А$ и заменить каждую букву $В$ на $АБ$, то получится палиндром. Действительно, пусть перед первой $В$ стояло $х_0$ букв $А$, между первой и второй - $x_i, \cdots$, после последней, $k$-й буквы $В - x_k$ букв $А$. Тогда $x_i = x_{k+1-i}$ при любом $1 \leq i \leq k$. В измененном слове перед первой буквой $Б$ будет $х_0 + 1$ букв $А$, между первой и второй - $x_i + 1, \cdots$, после последней, $k$-й буквы $Б - x_k + 1$ букв $А$. Поскольку $x_i + 1 = x_{k+1-i} + 1$, то полученное слово также будет палиндромом.
Пусть, скажем, Антоново слово из букв $А$ и $В$ разрезается на палиндромы $S$ и $T$. Пусть $S^{\prime}$ и $T^{\prime}$ - слова, полученные заменой $В$ на $АБ$. Если слово $T^{\prime}$ непусто, то $S^{\prime}А$ и $T^{\prime}А$ - палиндромы, слово $T^{\prime}$ начинается с $А (T^{\prime}А = AT^{\prime \prime}А)$, и поэтому $T^{\prime \prime}$ - тоже палиндром. Тогда Анино слово разрезается на палиндромы $S^{\prime}А$ и $T^{\prime \prime}$. Если же слово $T^{\prime}$ пусто, то $S^{\prime} = AS^{\prime \prime} (S^{\prime \prime}$ - палиндром) является требуемым разбиением. Доказательство для Бориного слова аналогично.
