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
Rights & Permissions

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

• News | 7 hours ago | 2

### Hopes Dashed for HIV Cure with Bone Marrow Transplant

• Reuters | 10 hours ago | 1

### Winter Storm Pushes Up U.S. East Coast after Deep-Freeze in the South

• Reuters | 12 hours ago | 2

### As Keystone Ruling Nears, Canada Short on Time for Climate Plan

• Reuters | 13 hours ago | 10

### Arctic Thaw Tied to European, U.S. Heatwaves and Downpours

• Reuters | 14 hours ago

More »

## Latest from SA Blog Network

• ### Gag Me With a Spoon: "Val-Speak" Takes Over SoCal

Cocktail Party Physics | 6 hours ago
• ### Nerds and Words: Week 49

Overthinking It | 13 hours ago
• ### Photoblogging: Muppet or Flamingo?

MIND
The Thoughtful Animal | 15 hours ago
• ### Sunday Species Snapshot: Fijian Monkey-Faced Bat

Extinction Countdown | 17 hours ago
• ### Right now, there's a giant blue chicken in Trafalgar Square

Tetrapod Zoology | 17 hours ago

## Science Jobs of the Week

Pinpointing a Polar Bear: Scientific American Magazine

X

Give a 1 year subscription as low as \$14.99

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