Frankin B. Given a square grid $n \times n$ where $n > 1$. A crossword is any non-empty set of its cells, and a word is any horizontal or vertical strip (a cell grid rectangle one cell wide) that is entirely composed of cells of the crossword and is not contained in any larger strip of cells of the crossword (neither horizontal nor vertical). Let $x$ be the number of words in the crossword, and $y$ the minimum number of words needed to cover the crossword. Find the maximum of the ratio $\frac{x}{y}$ for a given $n > 1$.
Example. For a rectangle \$nıtimes $2 \$$ we get $\$ \mathrm{x}=\mathrm{n}+2 \$, \$ \mathrm{y}=2 \$$.

Estimate. Method 1. Let there be $\$ z \$$ cells in the crossword. Choose some of its covering with the smallest number of words. Words from this covering are called correct, and the rest are called incorrect. Each cell is contained in no more than one horizontal and one vertical word. At least one of these words is correct, as correct words cover the entire crossword. Therefore, each cell belongs to no more than one incorrect word. Thus, the sum of the number of cells in incorrect words is no more than $\$ z \$$. If a cell is a word, then it does not adjoin another cell of the crossword either horizontally or vertically. Therefore, the cell is included in any covering of the crossword with words and, therefore, is a correct word. Therefore, all incorrect words contain no less than two cells, and the number of incorrect words is no more than $\$ \frac{z}{2} \$$.

Since correct words cover the entire crossword, the sum of the number of cells in them is no less than $\$ z \$$. Each word contains no more than $\$ n$ cells, so the number of correct words is no less than $\$ \frac{z}{n} \$$.

Thus, $\$$ \frac{x}{y} \leq 1 + \frac{z}{2} : \frac{z}{n} = 1 + \frac{n}{2} \$$, which is what we needed.

Method 2. Notice that if there are words of length 1, they must be included in any covering of the crossword. Therefore, they can be removed, and the ratio $\$$ \frac{x}{y} \$$ will not decrease, since $\$ x \geq y \$$.

Therefore, we assume that all words have a length of at least 2. Construct a bipartite graph where the vertices of the first part are all the words of the crossword, and the vertices of the second part are all the occupied cells (an edge connects two vertices if the word contains the cell). Consider those vertices of the first part that saturate the entire second part, let the sum of their degrees be $\$ \mathrm{~d} \$$.

In this case, $\$ \mathrm{~d} \leq n y \$$, since the degree of each of these vertices is no more than $\$ n \$$.

Since the degree of each of the other vertices of the first part is at least 2, the total number of edges in the graph is no less than $\$ \mathrm{~d} + 2(x - y) \$$.

In the second part, there are no more than $\$ \mathrm{~d} \$$ vertices, and the degree of each of them is no more than 2, so the number of edges in the graph does not exceed $2 \mathrm{~d} \$$.

Thus, $\$ \mathrm{~d} + 2(x - y) \leq 2 \mathrm{~d} \$$, which means $\$ 2(x - y) \leq \mathrm{d} \leq n y \$$, giving us the estimate.

## Answer

$1 + \frac{n}{2} \$$.

![](https://cdn.mathpix.com/cropped/2024_05_06_75db48f86176e8f64efag-03.jpg?height=166&width=1170&top_left_y=0&top_left_x=16)

Author: Shen A.X.

On the board, the letter A is written. It is allowed to, in any order and quantity:

a) prepend A to the left;

b) append B to the right;

c) simultaneously prepend B to the left and append A to the right.

For example, BABA can be obtained ( $A \rightarrow$ BAA $\rightarrow$ BABA), but ABBA cannot. Prove that for any natural number \$n \$, half of the words of length \$n can be obtained, and the other half cannot.

## Solution

For each word, for each of its letters, we calculate the difference between the number of B's to the left and the number of A's to the right. It is easy to see that when moving from one letter to the next to the right, this value increases by 1 if these two letters are the same, increases by 2 when moving from B to A, and does not change when moving from A to B. Letters for which this value is 0 are called central; it is clear that in any word there are no more than two such letters, and words of length $\$ n$ can be of four types:

1) those that have a central A and no central B;
2) those that have a central B and no central A;
3) those that have two central letters, and then these are adjacent AB;
4) those that have no central letters, then the word contains adjacent BA such that for B this value is -1.

By mapping a word of type 3 to the word obtained by transposing its central letters, we get a word of type 4. It is not difficult to see that this is a one-to-one correspondence (the inverse mapping is the replacement of BA with AB, where the value for B is -1).

Consider a word of type 1, move to the left from the central letter A until we encounter a letter B (or reach the end of the word), highlight all the passed A's (including the central one), and replace all highlighted A's with B's. This results in a word of type 2 (the central B will be the leftmost highlighted A), which we call the corresponding word to the original, and this correspondence is also one-to-one (the inverse mapping is constructed similarly).

Thus, the number of words of length \$n\$, which have a central A (words of type 1 and type 3), is the same as the number of words that do not have a central A (words of type 2 and type 4). It remains to show that exactly the words that have a central A can be obtained.

When applying any operation from the condition to any already written letter, the considered value does not change, so in all words that can be obtained from A, there is a central letter A. Conversely, by induction on the length of the word, it is easy to obtain that if a word has a central letter A, then it can be obtained (if the word ends with B, then this B can be removed and the induction hypothesis applied; if the word starts with A - remove the left A, otherwise remove the left B and the right A together).