3. Among any five nodes of a regular grid paper, there will definitely be two nodes, the midpoint of the segment between which is also a node of the grid paper. What is the minimum number of nodes of a grid made of regular hexagons that need to be taken so that among them, there will definitely be two nodes, the midpoint of the segment between which is also a node of this grid?

(A. Kulygin)

#
# Answer. 9

Lemma. Among any five nodes of a grid of equilateral triangles, there will be two such that the midpoint of the segment between them is also a grid node.

Proof. Introduce the origin at one of the grid nodes and denote by $\vec{a}$ and $\vec{b}$ the radius vectors to the two nearest nodes (see picture). Then the nodes of the grid are points of the form $m \vec{a}+n \vec{b}$ for integers $m$ and $n$. By the pigeonhole principle, among five points, there will be two points $m_{1} \vec{a}+n_{1} \vec{b}$ and $m_{2} \vec{a}+n_{2} \vec{b}$, for which the parity of $m_{1}$ and $m_{2}$ and the parity of $n_{1}$ and $n_{2}$ coincide simultaneously. The midpoint of the segment connecting these two points is the point $\frac{m_{1}+m_{2}}{2} \vec{a}+\frac{n_{1}+n_{2}}{2} \vec{b}$. It is a grid node due to the identical parity of $m_{1}$ and $m_{2}, n_{1}$ and $n_{2}$.

Solution. In the first picture, you can see an example of the placement of 8 grid nodes, among which there are no two such that the midpoint of the segment between them is a grid node. We will prove that nine nodes are sufficient. Note that the hexagonal grid is divided into the union of two triangular grids (see the second picture). By the pigeonhole principle, among any nine nodes, at least five will be in one of these two triangular grids. By the lemma, among these five nodes, there will be two of the required ones.

![](https://cdn.mathpix.com/cropped/2024_05_06_dcfac8f96fa27961912cg-1.jpg?height=297&width=387&top_left_y=1531&top_left_x=969)

![](https://cdn.mathpix.com/cropped/2024_05_06_dcfac8f96fa27961912cg-2.jpg?height=216&width=111&top_left_y=316&top_left_x=857)