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, one can 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 $\left(2^{14}-2\right)$ $-\left(2^{7}-2\right)=2^{14}-2^{7}$

## Answer

Author: Khramtsov D:

All cells of a square table $n \times n$ are numbered in some order with numbers from 1 to $n^{2}$. Petya makes moves according to the following rules. On the first move, he places a chip in any cell. Each subsequent move, Petya can either place a new chip in some cell or move a chip from a cell with number $a$ horizontally or vertically to a cell with a number greater than $a$. Each time a chip lands in a cell, that cell is immediately colored; placing a chip on a colored cell is prohibited. What is the minimum number of chips Petya will need to, regardless of the initial numbering, be able to color all the cells of the table in several moves?

## Solution

$n$ chips are sufficient. Indeed, one chip is enough for each row: it can be placed in the cell of the row with the smallest number, and then go through all the cells of the row in ascending order of numbers.

We will show that a smaller number of chips may not be enough. For this, we number the cells of one diagonal with the numbers $1,2, \ldots, n$, and number the other cells arbitrarily. Then one chip will not be able to visit two cells of this diagonal: if a chip lands on one of its cells, then the next move it must go to a cell with a number greater than $n$, and therefore, after that, it will not be able to return to the diagonal. Since a chip must visit each cell of the diagonal, Petya will have to use at least $n$ chips.

## Answer

$n$ chips.