# Meet the Neighbors

Image: Cloe Liane Shasha

• ### Perv

“As a sex writer, Jesse Bering is fearless—and peerless.” —Dan Savage “You are a sexual deviant. A pervert, through and through.” We may not want to admit...

David Shaw has returned to an early career. He designed some innovative parallel computers as an associate professor at Columbia University, went off to start a fabulously successful hedge fund and now has decided to simulate molecular dynamics calculations using vast parallelism.

A critical problem in such calculations is called the N-body problem which entails computing the future behavior of a collection of N objects (in our case, atoms) where the objects start with a velocity and position and each object exerts some force on all other objects. One must compute the trajectory of each atom as a function of all nearby atoms and some characterization of far-away atoms. My New York University colleague Leslie Greengard has developed a fundamental method (called "fast multipole") for the far-away atoms. Shaw and his colleagues have worked on how to lay out the near-atom problem on a parallel computer. I provide a reference at the end. The following puzzle, however, will abstract the problem to its essential core.

A bunch of office employees are placed in single-person cubicles along a very long, narrow poorly lit corridor. It is so narrow that only two people can pass one another at a time. The cubicles have numbers on the door starting at 0, so: 0, 1, 2, 3, ... (This numbering system is architecturally unusual but will be convenient mathematically.) We design the protocol of our solution as if we were looking at the hallway from the side, so we'll talk about people moving to the right and to the left.

Each person would like to shake hands with his or her three neighbors in the cubicles on each side (that is, the three to the right and the three to the left). Suppose that each handshake takes 10 seconds and passing from one cubicle to a neighboring one takes no time.

Warm-Up:
How long would it take if just one worker p wanted to shake hands with all six neighbors?

Solution:
Just 60 seconds. All the neighbors would come to p.

Of course, while person p meets his six neighbors, person p+7 could meet his six neighbors, so parallelism is possible. But our problem is to make everyone shake hands with his or her three neighbors to the left and his or her three neighbors to the right.

Here is one approach. Suppose that we handle people at locations p, p+4, p+8, etc., with respect to their three neighbors to the right. This can be done in 30 seconds. For example, p+1, p+2, and p+3 shake hands with p at the same time that p+4+1, p+4+2, and p+4+3 shake hands with p+4. In the next 30 seconds people at p+1, p+1+4, p+1+8 shake hands with their right neighbors. Altogether this takes 4 * 30 = 120 seconds.

1. However, 120 seconds is longer than necessary. How much better can we do?

Now, suppose that instead of one dimension, we had two dimensions. We have a large office with freestanding cubicles and each cubicle is surrounded by hallways on all four sides. The cubicles are numbered by their x and y coordinates starting at the lower left at (0,0). Each person wants to shake hands with everyone who is a “Manhattan distance” of two or fewer spaces away (that is, all neighbors two away horizontally and vertically as well as the immediate diagonal neighbors).

2. How can we do this and how much time will it take?

Let’s return to the single-corridor situation but now suppose that walking from cubicle to cubicle takes some time--say, one second per cubicle--but instead of shaking hands, office workers just glance at one another, taking zero time. Because of the bad lighting in the corridor, people will see one another properly only inside cubicles. A cubicle can fit no more than seven people.

3. How long should it take on a single corridor for all people to meet all six nearest neighbors?

Still open is how to solve the problem when participants don't know their cubicle number, and so don't know what their positions are, yet must nevertheless meet their nearest three neighbors.

Dennis's most recent puzzle book, Puzzles for Programmers and Pros, was published in May 2007 by John Wiley and Sons/Wrox

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 Magazine | 1 hour ago

### How Brain Scans Might Change the Way Doctors Diagnose Alzheimer’s

• Octopus Chronicles | 15 hours ago

### Octopus In Space: Why the Latest U.S. Spy Rocket Is More Appropriate Than the NRO Knows

• TechMediaNetwork | 15 hours ago | 5

### Radiation on Mars 'Manageable' for Manned Mission, Curiosity Rover Reveals

• News | 16 hours ago | 3

### Powder Rive Basin Coal on the Move

• TechMediaNetwork | 16 hours ago | 2

More »

## Latest from SA Blog Network

• ### The Search for a Nobel Prize-Winning Synapse Machine

MIND
MIND Guest Blog | 24 minutes ago
• ### Face Off! A Debate About Eating Anything With A Face

Food Matters | 57 minutes ago
• ### Freezing, Boiling, Dehydration and Starvation

Image of the Week | 2 hours ago
• ### Helen's Choice: Female Multiple Mating in the Natural World

The Primate Diaries | 3 hours ago
• ### Tuesday Tune: They Might Be Giants

Rosetta Stones | 5 hours ago

## Science Jobs of the Week

Meet the Neighbors

X

Give a 1 year subscription as low as \$9.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