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).
Any idea?
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.
Here is a solution with $k = 10, n = 17$:
I'll try to explain the procedure of how I constructed this image which could be used to create some other cases of n and k.
I realized that I could construct a polygon with a series of "pieces". I could place guards on a piece without these guards being made redundant by guards from different piece, so the pieces are independent from each other. I could then chain the pieces together any way I want.
My example polygon has 2 types of pieces: 1) A spike (one of these is colored yellow/orange) 2) A spike with a flat edge on the left side (one of these is colored green)
The spike piece uses 2 edges and allows 1 guard. The second type of piece uses 3 edges and allows 2 guards. Additionally I need an extra edge to connect my chain. By observing this I could count the number of edges in a polygon made up of x spikes, y flat-spikes, plus an extra edge to connect the ends of the chain with this equation:
$n = 17 = 2x + 3y + 1$
And similarly the number of guards that each chain allows:
$k = 10 = x + 2y$
Solve the system of equations for number of spikes = x and number of spike-edges = y. Solving this system of equations with different values of k and n would allow some other general answers.