Разделы 
Дополнительно
Задача по математике - 1131
2015-07-15 
Алфавит состоит из $n$ букв. Какова максимальная длина слова, если:
а) в нем две рядом стоящие буквы всегда различны;
б) из него нельзя получить вычеркиванием букв слова вида $abab$, где $a \neq b$?
Решение:
Если буква встречается только один раз, назовем ее буквой первого рода. В противном случае -буквой второго рода Буквы, рядом стоящие с буквой второго рода, различны, это следует из свойства б).
Если слово содержит хотя бы два вида букв, то оно содержит хотя бы одну букву первого рода. В противном случае мы можем получить из него слово вида $abab$, что противоречит условию. Вычеркнув все буквы второго рода, совпадающие с некоторой, получим слово из $n-1$ различных букв. Вычеркивая буквы второго рода и далее, придем к слову, состоящему только из букв первого рода.
Мы докажем методом математической индукции, что слово имеет длину не более $2n-1$ буквы.
Для $n=1$. Это утверждение правильно. Предположим теперь, что оно правильно для $n=k$ букв, и докажем его для $n=k+1$.
Пусть слово содержит $k+1$ различную букву, $\alpha$ - буква первого рода, а $\beta$ - соседняя с ней буква. Если $\beta$ - первого рода, то при вычеркивании $\beta$ возникает слово из $k$ различных букв, максимальная длина которого поэтому не превышает $2k-1$, а само исходное слово имеет длину не более $2k$.
Если $\beta$ - второго рода, то легко заметить, что или обе соседние буквы пары $\alpha$, $\beta$ различны, или имеется только одна соседняя буква, т. е. пара $\alpha$, $\beta$ стоит с краю.
Поэтому пару $\alpha$, $\beta$ можно вычеркнуть, оставшееся слово удовлетворяет условию а) задачи.
Длина оставшегося слова $2k-1$ буква, а первоначального - $2k-1+2 = 2(k+1) - 1$ буква.
Пример слова, имеющего $2k-1$ буквы, из алфавита $a_{1}, a_{2}, \cdots, a_{n}$:
$ a_{1} a_{2} a_{3} \cdots a_{n}a_{n-1}a_{n-2} \cdots a_{1}$.
Алфавит состоит из $n$ букв. Какова максимальная длина слова, если:
а) в нем две рядом стоящие буквы всегда различны;
б) из него нельзя получить вычеркиванием букв слова вида $abab$, где $a \neq b$?
Решение:
Если буква встречается только один раз, назовем ее буквой первого рода. В противном случае -буквой второго рода Буквы, рядом стоящие с буквой второго рода, различны, это следует из свойства б).
Если слово содержит хотя бы два вида букв, то оно содержит хотя бы одну букву первого рода. В противном случае мы можем получить из него слово вида $abab$, что противоречит условию. Вычеркнув все буквы второго рода, совпадающие с некоторой, получим слово из $n-1$ различных букв. Вычеркивая буквы второго рода и далее, придем к слову, состоящему только из букв первого рода.
Мы докажем методом математической индукции, что слово имеет длину не более $2n-1$ буквы.
Для $n=1$. Это утверждение правильно. Предположим теперь, что оно правильно для $n=k$ букв, и докажем его для $n=k+1$.
Пусть слово содержит $k+1$ различную букву, $\alpha$ - буква первого рода, а $\beta$ - соседняя с ней буква. Если $\beta$ - первого рода, то при вычеркивании $\beta$ возникает слово из $k$ различных букв, максимальная длина которого поэтому не превышает $2k-1$, а само исходное слово имеет длину не более $2k$.
Если $\beta$ - второго рода, то легко заметить, что или обе соседние буквы пары $\alpha$, $\beta$ различны, или имеется только одна соседняя буква, т. е. пара $\alpha$, $\beta$ стоит с краю.
Поэтому пару $\alpha$, $\beta$ можно вычеркнуть, оставшееся слово удовлетворяет условию а) задачи.
Длина оставшегося слова $2k-1$ буква, а первоначального - $2k-1+2 = 2(k+1) - 1$ буква.
Пример слова, имеющего $2k-1$ буквы, из алфавита $a_{1}, a_{2}, \cdots, a_{n}$:
$ a_{1} a_{2} a_{3} \cdots a_{n}a_{n-1}a_{n-2} \cdots a_{1}$.
