10,11 |  |

Authors: Bogdanov I.i., Podlipsky O.K.

Given natural numbers $a$ and $b$, where $a<b<2a$. On a grid plane, some cells are marked such that in every grid rectangle $a \times b$ or $b \times a$ there is at least one marked cell. For what largest $\alpha$ can we assert that for any natural number $N$, there exists a grid square $N \times N$ in which at least $\alpha N^{2}$ cells are marked?
Let's introduce a coordinate system on the plane such that the centers of the cells, and only they, have integer coordinates. We will say that a cell has the same coordinates as its center. We will call a rectangle $a \times b$ vertical or horizontal if its side of length $b$ is vertical or horizontal, respectively.

1. Let $D=a^{2}+(b-a)^{2}=2 a^{2}-2 a b+b^{2}$. Mark the cell $(0,0)$ and all cells obtained from it by integer multiples of the vectors $(a, b-a)$ and $(b-a, -a)$; the figure on the left shows an example of such a marking for $a=3, b=5$. The centers of these cells are located at the vertices of a square grid with side $\sqrt{D}$. Thus, the cells $(D, 0)=\left(a^{2}+(b-a)^{2},(b-a) a-a(b-a)\right)$ and $(0, D)$ are marked. Therefore, a marked cell transitions to another marked cell with a horizontal or vertical shift by $D$. From this, it is not difficult to conclude that in each

We will show that such a marking satisfies the condition; from this it will follow that $\alpha \leq D: D^{2}=1 / D$. Indeed, consider any strip of $b$ consecutive horizontal lines. Clearly, there is at least one marked cell in it. If $(x, y)$ are the coordinates of any marked cell in it, then one of the two cells $(x + a, y + (b-a))$ or $(x + (b-a), y - a)$ is also in this strip and is shifted from the previous one by no more than $a$ to the right. Therefore, in any $a$ vertical lines of our strip, there is a marked cell.

The proof for horizontal rectangles is analogous.
![](https://cdn.mathpix.com/cropped/2024_05_06_a3c8ec1189b8a5040576g-48.jpg?height=496&width=1314&top_left_y=362&top_left_x=380)

2. It remains to show that $\alpha=1 / D$ works. Consider an arbitrary marking that satisfies the condition. To each vertical rectangle, we associate any of the topmost marked cells in it. Let's estimate how many rectangles can be associated with one marked cell $A$; let its coordinates be $(0,0)$. It is contained in $a b$ vertical rectangles.

Consider a horizontal strip of cells whose ordinates are not less than 1 and not more than $a$. Let $B$ be the marked cell in this strip with the smallest non-negative abscissa, and $C$ be the marked cell in this strip with the largest negative abscissa (see figure on the right). Then there are no more than $b-1$ vertical lines between $B$ and $C$, otherwise, in our strip between these cells, there would be a horizontal rectangle without marked cells.

Now consider all $a(b-a)$ vertical rectangles containing $A$ and intersecting at least $a$ horizontal lines above $A$. Each of them contains $B$ or $C$, except for those located strictly between $B$ and $C$; there are no more than $(b-a)^{2}$ such rectangles. Therefore, at least $a(b-a)-(b-a)^{2}=(2 a-b)(b-a)$ rectangles containing $A$ also contain $B$ or $C$, and $A$ is not associated with them. In total, the cell $A$ is associated with no more than $a b-(2 a-b)(b-a)=D$ vertical rectangles.

Now let $N$ be an arbitrary number. Let $K=(a+b) N^{2}$ and consider an arbitrary $K \times K$ square; let there be $s$ marked cells in it. In this square, there are at least $(K-a)(K-b)$ vertical rectangles; each of them is associated with one of the $s$ marked cells. By the proven result, we get

$$
\text { s }
$$

Dividing our $K \times K$ square into $(a+b)^{2} N^{2}$ squares of size $N \times N$, we get that in one of them there are more than $\frac{N^{2}-1}{D}$ marked cells; therefore, there are at least $\frac{N^{2}-1}{D}+\frac{1}{D}=\frac{N^{2}}{D}$, which is what we needed.

## Answer

$\alpha=\frac{1}{2 a^{2}-2 a b+b^{2}}$,