
Problem T-4. Let $n$ be a positive integer. A square $A B C D$ is partitioned into $n^{2}$ unit squares. Each of them is divided into two triangles by the diagonal parallel to BD. Some of the vertices of the unit squares are colored red in such a way that each of these $2 n^{2}$ triangles contains at least one red vertex. Find the least number of red vertices.


Solution. The least number of red vertices is

$$
\left\lfloor\frac{(n+1)^{2}}{3}\right\rfloor
$$

First, we define a colouring and count the number of red vertices. In what follows it will be shown that the number of red vertices, obtained by this colouring, is indeed minimal.

It is convenient to replace the square by rhombus $A B C D$ as in this case the isosceles rightangled triangles are equilateral. Cover the rhombus by regular unit hexagons in such a way, that $A$ lies in the vertex of a hexagon (figure 1). Colour the center of each hexagon red. Clearly each equilateral unit triangle belongs to one of the hexagons and thus contains a red point. Hence this colouring satisfies the required conditions.

![](https://cdn.mathpix.com/cropped/2024_06_05_ded7ed172ed094285367g-15.jpg?height=637&width=935&top_left_y=1178&top_left_x=579)

Figure 1: Covering with regular hexagons.

Denote by $a_{n}$ the number of vertices which are coloured red. Let $A_{1}, A_{2}, \ldots, A_{n-1}$ be the points on $A B$ such that $A A_{1}=A_{1} A_{2}=\cdots=A_{n-2} A_{n-1}=A_{n-1} B=1$. Similarly define points $B_{1}, \ldots, B_{n-1}$ on $B C$, points $C_{1}, \ldots, C_{n-1}$ on $C D$, and $D_{1}, \ldots, D_{n-1}$ on $D A$.

Each of the $n$ points on the line $A_{1} B_{n-1}$ is red (figure 1 and 2 ). The parallel lines $A_{2} B_{n-2}$ and $A_{3} B_{n-3}$ have no red points while line $A_{4} B_{n-4}$ contains 3 points less than $A_{1} B_{n-1}$, that is $n-3$. All of them are red. Similarly, red points lie on lines $A_{7} B_{n-7}, A_{10} B_{n-10}$ and so on. The number of red points each time decreases by 3 . On the other side of the diagonal $A C$, we have $n-1$ red points on the line $C_{2} D_{n-2}, n-4$ points on $C_{5} D_{n-5}$ and so on. Hence the number of red points equals

$$
a_{n}=(n+(n-3)+(n-6)+\ldots)+((n-1)+(n-4)+(n-7)+\ldots)
$$

When $n$ is of the form $n=3 k+1$, we have $a_{n}=\frac{1}{3} n(n+2)$, for $n=3 k+2$ we get $a_{n}=\frac{1}{3}(n+1)^{2}$ and $n=3 k+3$ implies $a_{n}=\frac{1}{3} n(n+2)$. In general, $a_{n}=\left\lfloor\frac{1}{3}(n+1)^{2}\right\rfloor$.

![](https://cdn.mathpix.com/cropped/2024_06_05_ded7ed172ed094285367g-16.jpg?height=629&width=957&top_left_y=366&top_left_x=562)

Figure 2: The value of $a_{n}$.

Let $b_{n}$ denote the least number of red points needed. Clearly, $b_{1}=1$. Consider a triangle with side length 2 (the first picture on figure 3). The four unit triangles do not have a common vertex, hence at least two vertices must be coloured. Each of the small marked disjoint triangles in the second and third picture (figure 3) must contain at least one red vertex and the bigger marked triangle at least two. This implies that $b_{2} \geq 2+1=3$ and $b_{3} \geq 1+1+1+2=5$.
![](https://cdn.mathpix.com/cropped/2024_06_05_ded7ed172ed094285367g-16.jpg?height=298&width=1160&top_left_y=1518&top_left_x=472)

Figure 3: The minimum number of red vertices for $n=2$ and $n=3$.

It has thus been shown that for $n=1,2$, and $3, b_{n} \geq a_{n}$, which means that $b_{n}=a_{n}$. The rest will follow by induction. The next step will show that if $b_{n-3}=a_{n-3}$, then $b_{n}=a_{n}$.

Let $n=3 k+2$. As demonstrated in figure 4 , at least $b_{n-3}+(2 k+1) b_{2}$ red vertices are needed. That is,

$$
b_{n} \geq b_{n-3}+(2 k+1) \cdot 3=\left\lfloor\frac{(n-2)^{2}}{3}\right\rfloor+2 n-1=\left\lfloor\frac{(n+1)^{2}}{3}\right\rfloor=a_{n}
$$

hence $b_{n}=a_{n}$.

If $n=3 k+3$, we can estimate that

$$
b_{n} \geq b_{n-3}+2 k b_{2}+2+1+1+1=\left\lfloor\frac{(n-2)^{2}}{3}\right\rfloor+2(n-3)+5=\left\lfloor\frac{(n+1)^{2}}{3}\right\rfloor=a_{n}
$$

![](https://cdn.mathpix.com/cropped/2024_06_05_ded7ed172ed094285367g-17.jpg?height=357&width=596&top_left_y=388&top_left_x=754)

Figure 4: Case $n=3 k+2$.

![](https://cdn.mathpix.com/cropped/2024_06_05_ded7ed172ed094285367g-17.jpg?height=357&width=596&top_left_y=922&top_left_x=751)

Figure 5: Case $n=3 k+3$.

Finally, taking $n=3 k+1$, the last picture demonstrates that

$$
b_{n} \geq b_{n-3}+(2(k-1)+1) b_{2}+1+1+1+1=\left\lfloor\frac{(n-2)^{2}}{3}\right\rfloor+2 n-1=\left\lfloor\frac{(n+1)^{2}}{3}\right\rfloor=a_{n}
$$

In all the cases it follows that $b_{n}=a_{n}$.

![](https://cdn.mathpix.com/cropped/2024_06_05_ded7ed172ed094285367g-17.jpg?height=363&width=607&top_left_y=2074&top_left_x=748)

Figure 6: Case $n=3 k+1$.
