Zhendarov R.G.

Each side of an equilateral triangle is divided into $n$ equal segments, and lines parallel to the sides are drawn through all the division points. This triangle is divided into $n^{2}$ small triangular cells. Triangles located between two adjacent parallel lines form a strip.

a) What is the maximum number of cells that can be marked so that no two marked cells belong to the same strip in any of the three directions, if $n=10$?

b) The same question for $n=9$.
a) Examples are shown in the figures.
![](https://cdn.mathpix.com/cropped/2024_05_06_dadb5e48aa89908248cfg-17.jpg?height=538&width=1540&top_left_y=11&top_left_x=264)

Estimate. First method. Cut the triangle into four equal triangles using the midlines (left figure). Suppose we managed to mark a certain number of cells, with $a, b, c$, and $d$ cells falling into triangles $A E F, B D F, C D E, D E F$ respectively. Note that trapezoid $A B D E$ is covered by five strips parallel to side $A B$. Therefore, it contains no more than five marked cells, i.e., $a+b+d \leq 5$. Similarly, $b+c+d \leq 5$, and $a+c+d \leq 5$. Adding these three inequalities, we get $2(a+b+c+d)+d \leq 15$. Therefore, the total number of marked cells $a+b+c+d$ is no more than 7.

Second method. Suppose we managed to mark $k$ cells. Draw all three strips through each marked cell and count the total number $M$ of cells that fall into these strips (if a cell falls into several strips, count it with the corresponding multiplicity).

On the one hand, each of the 30 possible strips participates in the count as many times as there are marked cells in it (i.e., no more than once). All strips, taken once, cover the triangle three times, so $M \leq 300$.

On the other hand, the three strips passing through one marked cell "cover" (with multiplicity) no fewer than 39 cells. (Indeed, if the marked cell is at the left vertex of the triangle, the corresponding strips cover $19+19+1=39$ cells. When the marked cell is shifted to the adjacent cell to the right, one of the strips extends by 2, and the other two remain unchanged; with the next shift, one of the strips shortens by 2, and so on. Since shifts parallel to the sides of the triangle can reach any cell, the number of cells covered by the corresponding three strips will always be 39 for triangles pointing upwards and 41 for triangles pointing downwards).

Therefore, the strips corresponding to all marked cells cover no fewer than $39k$ cells, i.e., $M \geq 39k$. Thus, $39k \leq 300$, so $k \leq 7$.

b) Examples are obtained from the examples in part a) by cutting off the bottom strip.

Estimate. First method. Suppose we managed to mark a certain number of cells while satisfying the conditions. Only one of the cells marked with black dots can be marked. Due to their symmetric placement, we can assume that the bottom one of these cells is not marked. Cut the remaining part of the triangle into four pieces (see figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_dadb5e48aa89908248cfg-17.jpg?height=417&width=531&top_left_y=1824&top_left_x=775)

The same reasoning we used in the first method of part a) shows that the number of marked cells is no more than $(4+4+5): 2=6.5<7$.

Second method. Repeating the reasoning of the second method in part a), we get the inequality $35k \leq 243$, from which $k \leq 6$.

## Answer

a) 7; b) 6 cells.

Submit a comment