ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109776
Темы:    [ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
[ Индукция (прочее) ]
Сложность: 5+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .