Problem 9-4. From $n$ regular hexagons with side 1, a polygon on the plane was made by gluing hexagons along their sides. Any two hexagons either have exactly one common side or have no common points at all. There are no holes inside the polygon. Moreover, each hexagon has at least one side lying on the boundary of the polygon. What is the smallest perimeter that the polygon can have under these conditions?
Answer: $2 n+6$ for $n \geq 2$, $6$ for $n=1$.

Solution. It is easy to understand that if a point is an endpoint for at least one side of a hexagon, it is an endpoint for two or three sides: more than three is impossible because all angles are $120^{\circ}$.

Let's draw a bit. Imagine that in each point that is an endpoint for three sides of a hexagon, we place a red dot. And each path along the sides of the hexagons from a red dot to a red dot we outline with a blue marker. Thus, the blue lines go along the sides of the hexagons and through vertices from which only two sides emerge (in other words, which are vertices of exactly one hexagon). Note that the blue lines do not intersect except at their endpoints, which are red dots. It is easy to understand that if a point is an endpoint for at least one side of a hexagon, it is an endpoint for two or three sides: more than three is impossible because all angles are $120^{\circ}$.

Let's draw a bit. Imagine that in each point that is an endpoint for three sides of a hexagon, we place a red dot. And each path along the sides of the hexagons from a red dot to a red dot we outline with a blue marker. Thus, the blue lines go along the sides of the hexagons and through vertices from which only two sides emerge (in other words, which are vertices of exactly one hexagon). Note that the blue lines do not intersect except at their endpoints, which are red dots.

Thus, we have obtained a drawing of a multigraph on the plane. For it, Euler's formula $F-E+V=2$ holds, where $F, E, V$ are the number of faces, edges, and vertices, respectively. Since all vertices have degree $3, 3V = 2E$. Additionally, $F = n + 1$, since these are all the hexagons and the external face. From these three equations, we derive $E = 3n - 3$. Traversing the external cycle, we walked along all $n$ hexagons, so for $n > 1$, we changed the hexagon we were walking along at least $n$ times (note: this statement is not true if $n = 1$: we walked along one hexagon and never changed it). Thus, in the external cycle, there are at least $n$ edges, so in the rest of the graph, there are no more than $2n - 3$ edges. Each of these consists of exactly one segment that was a side for two hexagons, since inside the polygon, there cannot be points that are endpoints for exactly two side segments. Thus, inside there are no more than $4n - 6$ sides of hexagons, glued in pairs, so on the boundary, there are at least $2n + 6$ sides.

| Evaluation | Score | Content Criterion |
| :---: | :---: | :--- |
| + | 20 | Complete solution |
| .+ | 18 | Minor errors in the proof |
| $+/-$ | 14 | Significant gaps in the proof (e.g., existence of a hexagon touching others by no more than 2 sides is not proven) |
| $+/2$ | 10 | There is a statement that the minimum perimeter for $n$ and $n+1$ differs by 2, but the proof is missing. Example is provided |
| $-/+$ | 6 | There is an example for $2n + 6$. There is a statement that the minimum perimeter for $n$ and $n+1$ differs by 2, but the proof is missing |
| - | 0 | Solution is completely incorrect/only the answer |