11.5. The alphabet consists of $n$ letters. A word composed of these letters is called allowed if all adjacent letters in it are different and it is impossible to obtain a word of the form $a b a b$ by erasing letters from it, where the letters $a$ and $b$ are different. What is the maximum length that an allowed word can have?
Answer: $2 n-1$.

Solution. We will prove by mathematical induction. For $n=1,2$ - it is obvious. In an arbitrary word $w$ of $n+1$ letters, consider the leftmost letter, call it $a$. If it does not appear again in $w$, the remaining part of $w$ is a word of $n$ letters and, by the induction hypothesis, has a length not exceeding $2 n-1$. The total length of $w$ in this case does not exceed $2 n-1+1=2 n<2 n+1$.

If $a$ appears in $w$ at least one more time, the subwords into which $a$ divides $w$ do not share any letters. Otherwise, by removing everything except the first $a$, a letter $b$ that appears in different subwords, and the second $a$ between these $b$s, we would obtain the word $a b a b$, which is forbidden by the condition. Suppose $w$ contains $k$ occurrences of $a$, which divides $w$ into $k$ (if the last letter of $w$ is not $a$) or $k-1$ (if the last letter of $w$ is $a$) subwords, each using a non-overlapping set of letters. The length of each subword is estimated by induction as twice the number of distinct letters used in it, minus 1. In total, these subwords use $n$ letters, so the total combined length of all subwords does not exceed $2 n-(k-1)=2 n-k+1$. Adding the $k$ occurrences of $a$, we get that the length of $w$ does not exceed $(2 n-k+1)+k=2 n+1=2(n+1)-1$ - the induction step is proven.

Grading criteria. Any incorrect answer and an attempt to prove it: 0 points. An attempt to prove it relying on the fact that the longest word must necessarily have the form $a_{1} a_{2} \ldots a_{n} \ldots a_{2} a_{1}: 0$ points.