See Inside

# Pinpointing a Polar Bear [Preview]

Polar bears and gunners Image:

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.

Already a Digital subscriber? Sign-in Now

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Scientific American Mind | 21 hours ago | 5

### Why Do Top Athletes Suddenly Develop “the Yips”—a Tendency to Choke under Pressure?

• Scientific American Magazine | 21 hours ago | 3

### Swiss Cheese and Dust Devils: 7 High-Resolution Shots of Surface Activity on Mars [Slide Show]

• Octopus Chronicles | May 18, 2013

### Unusual Offshore Octopods: The See-Through "Glass" Octopus [Video]

• News | May 18, 2013 | 6

### Antarctic Neutrino Observatory Detects Unexplained High-Energy Particles

• Cocktail Party Physics | May 17, 2013

More »

## Latest from SA Blog Network

• ### 33 Years Ago Today...

Rosetta Stones | 10 hours ago
• ### Friday Weird Science: What's your fart volume?

MIND
The Scicurious Brain | 19 hours ago
• ### Physics Week in Review: May 18, 2013

Cocktail Party Physics | 20 hours ago
• ### Deadly Snakes, Ugly Critters, Leonardo DiCaprio and Other Links from the Brink

Extinction Countdown | 22 hours ago
• ### Unusual Offshore Octopods: The See-Through "Glass" Octopus [Video]

STAFF
Octopus Chronicles | May 18, 2013

## Science Jobs of the Week

Pinpointing a Polar Bear: Scientific American Magazine

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X