Kuyna A.K.

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, the midpoint of the segment between which is also a node of this grid?

#
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.

![](https://cdn.mathpix.com/cropped/2024_05_06_eab8c6bbe58aee0b55b3g-09.jpg?height=377&width=554&top_left_y=1935&top_left_x=755)

Proof of the lemma. Introduce the origin at one of the grid nodes and denote by $\$ \mid vec\{a\} \$$ and $\$ \operatorname{vec}\{b\} \$$ the radius vectors to the two nearest nodes, as shown in the figure. Then the grid nodes are points of the form $\$ m \mid vec\{a\} + n \mid vec\{b\} \$$ for integers \$m $\$$ and \$n\$. By the pigeonhole principle, among five points, there will be two points $\$ m_1 \mid vec\{a\} + n_1 \mid vec\{b\} \$$ and $\$ m_2 \mid vec\{a\} + n_2 \mid 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} \mid vec\{a\} + \frac{n_1 + n_2}{2} \mid vec\{b\} \$$, which is a grid node because the numbers $\$ \frac{m_1 + m_2}{2} \$$ and $\$ \frac{n_1 + n_2}{2} \$$ are integers due to the same parity of \$m_1 \$$ and \$m_2 \$$ and \$n_1 \$$ and \$n_2 \$$.

Solution. In the figure on the left, 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. Notice that the hexagonal grid can be divided into the union of two triangular grids (see the figure on the right). 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_eab8c6bbe58aee0b55b3g-10.jpg?height=395&width=577&top_left_y=97&top_left_x=869)

# Answer

9.

Submit a comment