# Meet the Neighbors

Image: Cloe Liane Shasha

• ### The Wisdom of Psychopaths

In this engrossing journey into the lives of psychopaths and their infamously crafty behaviors, the renowned psychologist Kevin Dutton reveals that there is a...

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

• Climatewire | 36 minutes ago | 1

### How Bad Is the Rebound from Energy Efficiency Efforts?

• In-Depth Reports | 1 hour ago

### Tornado Alley: Twister Devastates Oklahoma City Suburb

• News | 2 hours ago

### Search for Survivors Races On as 91 Feared Dead in Tornado-Hit Oklahoma

• Guest Blog | 2 hours ago

### Winning the War against Cervical Cancer

• Scientific American Mind | 3 hours ago

More »

## Latest from SA Blog Network

• ### USC Dornsife Scientific Diving: A New Faculty Member on the Team

Expeditions | 2 hours ago
• ### Winning the War against Cervical Cancer

Guest Blog | 2 hours ago
• ### Your Lady Parts Don t Like It When You Get Sick: Relationships Between Immune Health and Reproductive Hormones

Context and Variation | 3 hours ago
• ### Wild wallabies in the UK

Tetrapod Zoology | 4 hours ago
• ### #SciAmBlogs Monday - eating healthfully, DSM-5, polyploidy, fecal transplants, non-identical twins, and more.

STAFF
The Network Central | 12 hours ago

## Science Jobs of the Week

Meet the Neighbors

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