Imagine a research center in the Canadian Arctic. Unoccupied in the winter, the center consists of seven laboratory igloos linked by corridors. Each corridor connects two igloos. During a particularly harsh winter, a polar bear breaks into one of the igloos and starts wandering through the empty complex. The scientists must send a team to tranquilize the bear with a dart gun, but they don't know how many gunners to send. Safety rules specify that at least two gunners are needed to search an igloo and that they must approach the room together from the same corridor. But one person is enough to prevent the bear from coming into an igloo that has already been searched. A polar bear would find the corridors claustrophobic, so it would not hide there. Instead it would run from igloo to igloo, and because the animal moves so quickly (much faster than the gunners) the transit time is essentially zero.

Suppose that the complex has a wheel-and-spoke pattern, with one igloo at the center and six at the perimeter. In this case, four gunners are enough to track down the bear [see illustrations 1 through 3 at right]. But what if the scientists have forgotten the exact layout of the research center? All they know for certain is that there is at most one corridor connecting one igloo to another and that the corridors don't meet or cross one another. (Mathematicians call this topology a planar graph.) An example of such a pattern is shown in illustration 4. The gunners can start at any igloo. What is the fewest number of gunners that can be sent?

Now suppose there are 100 igloos arranged in a rectangular grid. Each igloo has corridors leading to its horizontal and vertical neighbors (no diagonal corridors are allowed). What is the smallest team of gunners that can do the job?

This article was originally published with the title Pinpointing a Polar Bear.

Comments