## Task A-1.5.

In some language, every word is a string of letters $a$ and $b$. Each word has at least one and at most 13 letters, but not all such strings are words. It is known that by concatenating one word to another, we never get a word. Determine the maximum possible number of words in this language.
## Solution.

Notice that for each $k=1,2, \ldots, 13$, the total number of sequences of letters $a$ and $b$ of length $k$ is $2^{k}$ (for each position in the word, we choose one of two letters), so the total number of sequences of length between one and 13 is $2^{1}+2^{2}+\cdots+2^{13}=2^{14}-1$.

Consider a language in which the words are all sequences of letters of length 7 or more. It is clear that the condition in the problem is satisfied: by concatenating two such words, we get a sequence of characters longer than 13, so it definitely does not belong to the language. The total number of such words is $2^{7}+2^{8}+\cdots+2^{13}=2^{14}-2^{7}$.

We will prove that this is the maximum number of words that can be found in a language. A language with the most words in which no word is shorter than 7 is described above. Now consider any language in which there is at least one word shorter than 7 and call it $X$. For any sequence $Y$ of characters of length 7, let $X+Y$ be the sequence of characters formed by concatenating the word $X$ and the sequence $Y$. The length of this sequence is less than 13.

For all possible sequences of characters $Y$ of length 7, consider sets of the form $\{Y, X+Y\}$. Since the word $X$ is in the language, at least one of the sequences of characters $Y$ and $X+Y$ is not a word. Since there are $2^{7}$ such two-element sets (as there are sequences of characters of 7 letters), at least that many sequences of characters are not words. We conclude that this language can have at most $\left(2^{14}-1\right)-2^{7}$ words.

Thus, if no word in the language is shorter than 7, it can have at most $2^{14}-2^{7}$ words, and if there is at least one word in the language of length less than or equal to 7, it can have fewer words. Therefore, the maximum number of words in the language is $2^{14}-2^{7}=16256$.

## NATIONAL MATHEMATICS COMPETITION

## 2nd grade - high school - A variant

## May 11, 2021.