Solution

You just explored the Gallery Problem, which is a typical problem from the field of Applied Mathematics. Other applications of this problem include steering a robot through an obstacle course; and computer pattern recognition, such as adding color to old black and white movies. The computer must recognize a certain shape in each digitized frame, a sofa for example, and add a color to it.

The solution to this puzzle involves two "techniques": triangulation of the polygon and graph coloring.

Triangulation of the polygon: Our gallery has 11 walls, and 11 vertices, or corners. The first step in our solution calls for drawing line segments connecting the vertices so that all interior regions of the polygon are bounded by a triangle. The line segments cannot cross each other or go outside the polygon.

Graph coloring: The next step calls for assigning colors to the vertices with the requirement that adjacent vertices have different colors. The solution uses three colors: red, green, and blue. The tri-coloring of the graph is allowed by a proof based on induction on n, the number of edges of the polygon.

The solution: Triangulate the polygon. This will yield 9 triangles. Next color the graph. Note that each triangle will have one corner of each color.

For a graph with n corners and 3 colors, some color will be used on n / 3 or fewer corners. For a gallery with 11 corners and 3 colors, one color is used at most 3 times while the other two are each used four times. Therefore the fewest number of guards required to watch the gallery is 3.

 

Back to Puzzle