Mapcraft

Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992), Database Tuning: A Principled Approach (Prentice Hall, 1992), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at [email protected].

With his silver hair, piercing eyes, and Oxbridgian prosody, Henry Pencil looked and sounded much the distinguished elder statement he in fact was. The furrows in his brow, though, revealed a sadness characteristic of some who had seen too much suffering -- or had felt it too deeply.

"The paradox of modern time is that communication and transport have become nearly instantaneous, enabling people to communicate and mingle as never before, yet ethnic tension becomes ever more brutish," he began in a oratorical tone. "Two years ago, the Czech Republic and Slovakia both applied to the Common Market, an internationalist step. At the same time, the two peoples simmer with resentment towards one another to such an extent that friendships founder on the question of ethnicity. We see this pattern all over the world: Catalonia and Spain, Armenia and Azerbaijan, not to mention the Balkans, the Middle East and Asia. Statesmen can sometimes bring peace (I pray it works in Northern Ireland), but seldom for long. Sooner or later, I'm afraid, a population exchange takes place, often a bloody one. Witness the bloodshed after the Indian subcontinent became independent in 1948. I want to reduce the pain of this process mathematically, and I want your help.

"A new ethnic rivalry has arisen in middle Europe and we want to create a population exchange plan. We have divided the area into a 10×10 grid. Each cell contains a homogeneous population. Remarkably, each cell also enjoys roughly the same natural resources.

"We want to find the fewest exchanges that cause each group to have a continuous region. A region for group X is continuous if one can travel from any cell in region X to any other cell in region X without having to pass through the cell of another group."

Ecco stopped Pencil, "In your grid, do you count two cells to be adjacent if they border each other on the diagonal?"

"No, only if they border horizontally or vertically," Pencil answered.

I thought I understood.

"Ecco, graph theoretically," I said. "He means that each group should live in one connected component, where each cell in the grid is a node, and there is an edge between two nodes if they border each other horizontally or vertically."

Pencil nodded and showed us a piece of paper. "Yes, the mathematicians in U3 have formulated the problem exactly that way. But that doesn't help bloody much. The question is how to achieve this state.

"The history of population exchanges is sad. In 1948, for example, mobs attacked the trains carrying Muslims leaving India, and trains carrying Hindus leaving Pakistan. Also, the homes each side left for the future occupants were in horrible disrepair. Some were burnt to the ground. We want to manage this exchange much better: All exchanges will be pairwise. The heads of the exchanging cells will meet to assure one another that they will leave their villages in good shape. UN soldiers will try to prevent looting."

"If everyone is going to be so reasonable, then maybe they can just keep their homes and live in peace," Liane said.

Pencil let out a sigh. "I wish I could share your optimism, young lady," he said to 10-year-old Liane. "But the land suffered from riots last year and tensions are quite high."

"Very well, we will help you," Ecco said. "Please give us the current grid."

"Wait. I still don't understand the problem," Liane interrupted. "Could you give a small example so we can be sure to understand the problem?"

"Capital idea," said Pencil, smiling for once. "Please understand that we represent each group by a number 0, 1, or 2. Suppose we had a 5×6 grid:

2 1 2 1 0

1 0 1 1 2

1 2 1 1 0

1 0 1 0 0

2 0 1 2 1

0 0 0 0 0

"Here is a transformed state that meets our conditions:

1 2 2 2 2

1 1 2 1 2

1 1 1 1 0

1 0 1 0 0

1 0 1 0 0

0 0 0 0 0

"Notice that it is possible to go from any cell to any other of the same group by walking vertically or horizontally and remain within the same group at all times. How many exchanges would it take you to achieve the transformed state?"

Liane thought for only a few minutes and then said, "Would six be too many? Here they are:

exchange 1: exchange (0 0) for (0 3)

Continue exchanging as follows:

exchange (0 4) with (4 3)

exchange (1 1) with (2 3)

exchange (2 1) with (1 2)

exchange (4 0) with (0 1)

exchange (4 4) with (2 3)

"Not bad," Pencil said. "Not at all bad. It took our best mathematicians a bit longer than it took you. Here now is our real problem. Please see what you can do. Any number of exchanges under 20 would be fine. We won't specify the transformed state. We just ask you to produce -- what did you call them -- a single connected component for each group. Please see how few exchanges you can use."

0 0 0 1 0 1 2 0 2 0

2 2 2 2 1 0 0 0 0 1

2 2 1 2 2 1 1 0 1 2

2 2 1 1 1 2 0 1 2 0

1 1 1 2 2 1 0 2 1 1

1 2 1 2 2 0 0 1 1 0

2 0 0 2 0 0 1 1 1 1

1 2 1 2 1 0 1 1 0 1

1 0 2 1 2 1 0 2 2 1

0 2 1 1 1 0 1 1 0 1

Ecco and Liane worked together and came up with an appropriate state after only 15 exchanges.

"We really wish you could find a more imaginative solution to this problem, Mr. Pencil," Ecco said as he handed Pencil the solution. "Perhaps a national juggling team?"

Reader: Can you find 15 or fewer exchanges to achieve a state in which each group has a continuous region? Send your solution to me at [email protected].

Last Month's Solution

The solution uses Liane's observation. Fred could be winning by between $100,000 and $110,000; between $110,000 and $120,000 and so on, up to between $390,000 and $400,000. Similarly, he could be losing that much. So, the basic strategy works this way:

Let Fred's initial winning or losing position be called p. Try to flip so that Fred will reach p+$115,000; p-$115,000; p+$125,000; p-$125,000; and so on up to p+$395,000 and p-$395,000 or until he gets in-bounds. This gives 60 positions to search for. On the average, he will have to explore 30 of them before getting within bounds. Call these the "targets."

By aiming for each target individually, one's expected time would be two flips per target. Since, on the average, one will be in-bounds after exploring 30 targets, this results in a requirement of 60 flips.

Ecco's technique does slightly better (the expected number of flips is 55), because even when he misses a target, he may hit another target. For example, if he flips for $115,000 the first time and then $230,000 the second time, he will cover either p+$115,000 and p-$115,000; or p+$115,000 and p+$345,000 (115,000+230,000); or p-$115,000 and p-$345,000.

This advantage is particularly pronounced in the case where in-bounds is plus or minus $1,000 from 0.

Liane tried a few thousand experiments. In roughly 30 percent of them, Fred was down more than $10 million before becoming in-bounds. In nearly 0.4 percent of them, Fred was down more than $1 billion. Ecco's strategy is pretty dangerous for Fred if he has a limited budget.

Reader Solutions for Lines of Fire

For "Lines of Fire" (DDJ, July 1998), several readers showed that if Solo can occupy three hills to begin with, there are about 40 such sets that can fire upon all other hills. When Solo can occupy two hills to begin with, there are several pairs that work. The interesting question was what to do when Solo could occupy only one hill to begin with. It turns out, he cannot accomplish his mission. Here is the idea of the proof following a combination of the formulations of Ralph Nebiker, Michael S. VanVertloo, and Christian Tanguy:

Define a safe hill as one that can fire upon all hills that can fire upon it. Both 0 and 16 are safe and the adversary will be able to capture at least one of them after Solo's first move. In either case, the adversary will later be able to capture another hill that will give the adversary control over 18 hills. This is enough to prevent Solo from accomplishing his mission.

Here were some of the talented readers who found a proof like this or used exhaustive search to show that Solo could not win with only one hill. Congratulations to the other readers who found many solutions to the first two problems.

Ralph Nebiker

Gary Knowles

Bill Wade

Kakulidis Iulianos

Matthew Davies

Christian Tanguy

Thorsten Koch

Michael S. VanVertloo

Russ Lyttle (who used colored paper and transparencies instead of a computer).

DDJ