I am stuck on a problem related to art galleries. It is problem $12$ in the chapter about art galleries in How to Guard an Art Gallery and Other Discrete Mathematical Adventures by T.S. Michael (I slightly edited the question, mostly to introduced notations $k$ and $n$):
Post $k=10$ guards in a particular art gallery with $n=17$ walls so that the entire gallery is protected, but the dismissal of any guard leaves some part of the gallery unprotected.
The difficulty is clearly that the art gallery in the problem is an unknown that should be determined. I tried many examples of galleries with $17$ walls but so far, I can only find an example for the simpler problem with $k=8$ (a star-shaped gallery).
Background if you don't know about art galleries but want to try to solve the problem:
- An art gallery with $n$ walls is represented by a nonconvex polygon with $n$ edges.
- A guard is represented by a point. The guard can be positioned anywhere in the gallery, including along a wall or at a vertex.
- Guards cannot move, but can see all around them (at once!). They A point $p$ in the interior of the gallery is seen by a guard $g$, if $[p,q)$ is contained in the interior of gallery.
- A gallery is protected if any point in its interior is seen by at least one guard.