|
|
 |
Условие
На доске написана буква А. Разрешается в любом порядке и количестве:
а) приписывать А слева;
б) приписывать Б справа;
в) одновременно приписывать Б слева и А справа.
Например, БААБ так получить можно (A → БAA → БААБ), а АББА – нельзя. Докажите, что при любом натуральном $n$ половину слов длины $n$ получить можно, а другую половину – нельзя.
Решение 1
Для каждого слова, для каждой его буквы подсчитаем разность количества букв Б слева и букв А справа. Легко видеть, что при переходе от буквы к соседней справа эта величина увеличивается на 1, если эти две буквы одинаковые, увеличивается на 2 при переходе от Б к A, не изменяется при переходе от А к Б. Буквы, для которых эта величина равна 0, назовём центральными; понятно, что в любом слове их не более двух, при этом слова длины $n$ бывают четырёх типов:
1) в которых есть центральная A и нет центральной Б;
2) в которых есть центральная Б и нет центральной А;
3) в которых есть две центральные буквы, и тогда это рядом стоящие АБ;
4) в которых нет центральных букв, тогда в слове есть рядом стоящие БА такие, что для Б наша величина равна –1.
Поставив слову типа 3 в соответствие слово, получающееся транспозицией его центральных букв, получим слово типа 4. Нетрудно видеть, что это взаимно однозначное соответствие (обратное отображение – смена БА на АБ, где у Б величина равна –1).
Рассмотрим слово типа 1, пойдём влево от центральной буквы А, пока не встретим букву Б (или не дойдём до конца слова), выделим все пройденные буквы А (включая центральную), заменим все выделенные буквы А на буквы Б. Получится слово типа 2 (центральной Б будет полученная из левой выделенной А), которое назовём соответственным исходному, это соответствие тоже взаимно однозначно (обратное отображение строится аналогично).
Таким образом, слов длины $n$, в которых есть центральная А (слова типа 1 и типа 3), столько же, сколько слов, в которых центральной А нет (слова типа 2 и типа 4). Остаётся показать, что получить можно в точности слова, в которых есть центральная А.
При применении любой операции из условия для любой уже написанной буквы рассмотренная величина не меняется, поэтому во всех словах, которые можно получить из А, есть центральная буква А. Обратно, индукцией по длине слова легко получить, что если в нём есть центральная буква А, то его можно получить
(если слово заканчивается на Б, то эту Б можно выкинуть и применить предположение индукции; если слово начинается на A – выкинем левую А, а иначе можно выкинуть вместе левую Б и правую А).
Решение 2
Назовём слова, которые можно получить из А указанными операциями, допустимыми. Докажем сначала следующий критерий того, что слово допустимо. Надо подсчитать общее число букв А в слове, пусть это $k$, и посмотреть, какая буква стоит в слове на $k$-м месте слева: если там А, то слово допустимо, а если Б – нет (если $k$ = 0, то слово тоже недопустимо).
Ясно, что все допустимые слова удовлетворяют критерию: изначально он выполнен (одна буква А на первом месте), а далее при каждом приписывании сохраняется (нетрудно проверить).
Обратно, пусть слово удовлетворяет критерию. Удаляя слева буквы А по одной, мы, очевидно, сохраняем критерий, то же верно при удалении справа букв Б по одной. Дойдя так слева до буквы Б, а справа – до А, можем удалить эту пару, сохраняя критерий. Такими операциями можно прийти к одной букве, и это обязательно А, так как для неё критерий должен выполняться.
Решим теперь задачу. Будем считать, что $n$ > 1 (для $n$ = 1 задача очевидна). Общее число допустимых слов можно подсчитать так: допустимые с одной А, с двумя А, ..., с $n$ буквами А.
Рассмотрим допустимые слова с $k$ буквами А, где 0 < $k < n$. Чтобы их подсчитать, надо зафиксировать на $k$-м месте букву А и расставить на оставшихся местах $n - k$ букв Б, остальное заполнить буквами А.
Но ровно столько же будет недопустимых слов с $n - k$ буквами А, у которых на ($n-k$)-м месте стоит буква Б: их количество вычисляется аналогично. Суммируя по $k$ от 1 до $n$ – 1 и добавляя допустимое слово А...А и недопустимое слово Б...Б, получаем все допустимые и все недопустимые слова, причём их количества равны.
Решение 3
Назовём слова, которые можно получить, достижимыми. Всего существует $2^n$ различных слов длины $n$, поэтому достаточно доказать, что количество достижимых слов длины $n$ равно $2^{n-1}$. Докажем это по индукции.
База. Для $n$ = 1 и $n$ = 2 это легко проверяется: А → АА, А → АБ.
Шаг индукции. Посмотрим, как можно получить слово длины $n$ + 1:
1) из слова длины $n$, применив операцию а): W → АW;
2) из слова длины $n$, применив операцию б): W → WБ;
3) из слова длины $n$ – 1, применив операцию в): W → БWА.
Слов 1-го и 2-го типа по $2^{n-1}$, а слов 3-го типа – $2^{n-2}$. При этом слова 3-го типа не могут совпадать со словами 1-го и 2-го типа. А вот множества слов 1-го и 2-го типа пересекаются. Их общие слова имеют вид AWБ. Докажем, что слова W (которые находятся между буквами А и Б) – это все достижимые слова длины $n$ – 1. Понятно, что если W – достижимое слово, то за две операции из него можно получить АWБ. С другой стороны, если слово WБ достижимо, то посмотрим, как оно было получено. Если проделать все те же операции, но пропустить приписывание последней буквы Б, то будет получено слово W, значит, оно достижимо.
Таким образом, общих слов 1-го и 2-го типа столько же, сколько достижимых слов длины $n$ – 1, то есть $2^{n-2}$. Следовательно, количество слов длины $n$ + 1 равно
$2^{n-1}$ + $2^{n-1}$ – $2^{n-2}$ + $2^{n-2}$ = $2^n$, что и требовалось.
