The Art and Craft of Problem Solving

2.4 OTHER IMPO RTANT STRATEGIES 55

is placed, will occupy exactly one black and one white square. The 31 dominos thus

require 31 black and 31 white squares, so tiling is impossible. _

The idea of introducing coloring to reformulate a problem is quite old. Never­
theless, it took several years before anyone thought to use this method on the Gallery
Problem (Problem 2.2.26 on page 38). This problem was first proposed by Victor Klee
in 19 73, and solved shortly thereafter by Vaclav Chvatal. However, his proof was
rather complicated. In 19 78, S. Fisk discovered the elegant coloring argument that we
present below.^7 If you haven't thought about this problem yet, please do so before
reading the solution below.

Example 2.4.3 Solution to the Gallery Problem: If we let g(n) denote the minimum

number of guards required for an n-sided gallery, we get g(3) = g(4) = g(5) = 1 and

g( 6) = 2 by easy experimentation. Trying as hard as we can to draw galleries with

"hidden" rooms, it seems impossible to get a 7-sided or 8-sided gallery needing more

than two guards, yet we can use the idea of the 6-sided, two-guard gallery on page 38

to create a 9-sided gallery, which seems to need three guards. Here are examples of an

8-sided and 9-sided gallery, with dots indicating guards.

If this pattern persists, we have the tentative conjecture that g(n) = Ln/3J. A key

difficulty with this problem, though, is that even when we draw a gallery, it is hard

to be sure how many guards are needed. And as n becomes large, the galleries can

become pretty complex.

A coloring reformulation comes to the rescue: Triangulate the gallery polygon.

Recall that we proved, in Example 2.3.9 on page 48, that we can color the vertices

of this triangulation with three colors in such a way that no two adjacent vertices are

the same color. Now, pick a color, and station guards at all the vertices with that

color. These guards will be able to view the entire gallery, since every triangle in the

triangulation is guaranteed to have a guard at one of its vert ices! Here is an example

of a triangulation of a 15 -sided gallery.

(^7) See [22] for a nice discussion of Chvatal's proof and [ 3 1] for an exhaustive treatment of this and related
problems.