How many watchmen are needed to guard the art gallery at left, so that every part of it is under surveillance? The answer in this case is 4; four guards stationed as shown will be able to watch every part of the gallery.

In 1973 University of Montreal mathematician Václav Chvátal showed that, in a gallery with n vertices, n/3 guards will always be enough to do the job. (If n/3 is not an integer, you can dispense with the fractional guard.) And Bowdoin College mathematician Steve Fisk found a beautifully simple proof of Chvátal’s result.

The figure at right shows another art gallery. Cut its floor plan into triangles, and color the vertices of each triangle with the same three colors. The full area of any triangle is visible from any of its vertices, and that means that the whole gallery can be guarded by stationing watchmen at the points indicated by any of the three colors. Choosing the color with the fewest vertices will give us n/3 guards (again discarding fractional guards).

The Chvátal and Fisk proofs both give an answer that’s sufficient but sometimes not necessary. In this case, the gallery has 12 vertices, and 12/3 guards (say, the four green ones) will certainly do the job, but here as few as two will be enough.

(Steve Fisk, “A Short Proof of Chvátal’s Watchman Theorem,” Journal of Combinatorial Theory, Series B 24:3 [1978], 374.)