Bogdanov I.I.

In the language of the AU tribe, there are two letters - "a" and "u". Some sequences of these letters are words, and each word has no fewer than one and no more than 13 letters. It is known that if you write down any two words in a row, the resulting sequence of letters will not be a word. Find the maximum possible number of words in such a language.

#
If all sequences, the number of letters in which is not less than 7 and not more than 13, are words, then, obviously, the condition of the problem is satisfied; in this case, the number of such words is $2^{7}+\ldots+2^{13}=2^{14}-2^{7}$. It remains to show that this number is the largest possible.

The first method. The total number of sequences of length not exceeding 13 is $2+2^{2}+\ldots+2^{13}$ $=2^{14}-2$. If there is not a single 7-letter word among the words in the language, then the total number of words does not exceed $2^{14}-$ $2-2^{7}$ $2^{7}-2$ sequences. Therefore, it is possible to associate each sequence $a \in A$ with a sequence $b_{a} \in B$ such that all sequences $b_{a}$ are different. Note that then all sequences of the form $a b_{a}$ are also different (since their 7-letter endings are different).

By the condition, in each of the $2^{7}-2$ triples $\left(a, b_{a}, a b_{a}\right)$, there are no more than two words of the language. Consequently, at least $2^{7}-2$ sequences of 13 or fewer letters are not words, and the total number of words is no more than ( $2^{14}-2$ ) $-\left(2^{7}-2\right)=2^{14}-2^{7}$

## Answer

$2^{14}-2^{7}=16256$ words.