A museum gallery is in the shape of a concave $n$-gon. Guards need to be placed in the room so that every point on every wall is visible from some guard's position. What is the maximum number of guards needed?
We will show that $\left[\frac{n}{3}\right]$ guards are always sufficient, and there exists an $n$-gon for which this many are also necessary.

First, we prove the necessity. If $n=3k$, consider the $n$-gon shown in the diagram.

In this $n$-gon, no two of the vertices $A_{2}, A_{5}, \ldots, A_{3k-1}$ can be seen from the same position (in the diagram, we have shaded the regions from which these vertices can be seen), so at least $k$ guards are needed. If $n=3k+1$ or $n=3k+2$, then by inserting one or two additional vertices, respectively, we can divide the side $A_{1}A_{3k}$ into two or three parts. Thus, we have shown that there exists an $n$-gon for which at least $\left[\frac{n}{3}\right]$ guards are needed.

To prove the sufficiency, first divide the $n$-gon into $n-2$ triangles using $n-3$ diagonals. It is well-known that this is always possible (see, for example, János Surányi: Mathematical Competition Problems, Volume III, p. 59, Tankönyvkiadó, Bp., 1992). We will show by complete induction that the vertices can be colored with three colors such that in each triangle of the decomposition, the three vertices have different colors. This is trivial for $n=3$. If $n \geq 4$, there is a triangle that lies on two sides of the $n$-gon. (For example, because there are more sides than triangles, and a triangle cannot lie on three sides.) This triangle is bounded by two adjacent sides of the $n$-gon, and its third side is a diagonal. If we remove this triangle, the remaining $(n-1)$-gon can be colored. The two vertices of the removed triangle have been colored with different colors, because the diagonal is also a side of another triangle. Therefore, we can choose an appropriate color for the third vertex.

Thus, color the vertices with three colors, and consider the color that appears the least frequently. By placing a guard at each vertex of this color, the guards will see every wall and every interior point of the polygon, and their number cannot exceed $\frac{n}{3}$.

From the work of Nikolett Győri (Fazekas M. Főv. Gyak. Gimn., I. o.t.) and László Lukács (Miskolc, Földes F. Gimn., II. o.t.)

![](https://cdn.mathpix.com/cropped/2024_05_02_575b600d1953562ec132g-1.jpg?height=293&width=987&top_left_y=1106&top_left_x=580)