Fair Swedes

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].

When I arrived at Ecco's house the first cool week of October, I was surprised but delighted to see Evangeline. She had spent the summer in the math department at Uppsala, Sweden. Now, she was back at Princeton pursuing what she called "molecular logics." (She once tried to explain it as "logic without labels," but we were interrupted before I could hear more.)

"What surprised me most was that they really believe that philosophy is important at Uppsala," she was saying to Ecco. "They think that people who subscribe to the consensus-based socialism embodied in the Swedish political economy will invent a certain kind of mathematics."

"And do they?" Ecco asked.

"In subtle ways," Evangeline answered.

"The pattern-recognition techniques scientists develop there are based on the Demster-Schaefer theory, which works by eliminating disagreements among different data sources."

"Maybe they're on to something," Ecco allowed.

"They asked me to work on a different kind of voting, Jake," Evangeline went on. "I think they wanted me to discuss it with you and it seems difficult enough that you might like to hear it."

Ecco nodded, "Please proceed."

"Götoldenborg is one of the oldest cities in Sweden," Evangeline said. "It is really a large village, having a population of about 170,000. That population has been shrinking of late, so the Swedish government has decided to reduce the number of districts from 66 to 28. The goal is to create districts, each having roughly 6000 people, give or take 100 people.

"This is the problem they wanted your help with," Evangeline said, as she handed Ecco a map outlining the districts (Figure 1).

"The numbers are in a funny arrangement," Ecco said.

"I said that, too," Evangeline replied, laughing. "They are numbered in the order that each area became a town. Götoldenborg is really the conglomeration of several small towns."

"What are the constraints on the solution?" Ecco asked.

"First, each district must be connected," Evangeline replied. "That is, it must be possible to walk from anywhere within a district to anywhere else within that district without passing through any other district, much as in the population-exchange problem you mentioned to me a few months ago.

"Second, each district should have 6000 people, as I mentioned before. Third, you should never divide an existing district to create a new one. This table (see Table 1) shows the current populations."

Reader: Find a mapping from the original 66 districts to 28 districts such that each district has close to 6000 inhabitants (within 100), each district is connected, and no existing district is divided up.

Last Month's Solution

When one nasty person wants to drop off 13 postcards, then 150 minutes suffice. Here's how: Go from (4,0) to (4,3) arriving at time 30. Switching trains takes 10 minutes, so beginning at time 40, go to (0,3) arriving at time 80. After switching for 10 minutes (time 90), take the train to (0,1) arriving at time 110. After switching for 10 minutes (time 120), take the train to (3,1) arriving at time 150.

When one nasty person wants to drop off 19 postcards, then 250 minutes suffice. Here's how: Go from (4,0) to (4,3) arriving at time 30. Switching trains takes 10 minutes, so beginning at time 40, go to (0,3) arriving at time 80. After switching for 10 minutes (time 90), take the train to (0,1) arriving at time 110. After switching for 10 minutes (time 120), take the train to (2,1) arriving at time 140. After switching for 10 minutes (time 150), the agent finds a train going east (because the line between (2,0) and (2,4) starts 20 minutes late), reaching (2,4) at time 180. Then, at time 200, there is a train going the other way all the way to (0,0) at time 250.

If two nasty people work for 80 minutes, they can drop off 16 cards. The first nasty person takes the route that Liane suggested: (0,0), (1,0), (2,0), (3,1), (3,2), (2,4), then switches to (1,4) and (0,4). The second nasty person takes the route (0,3), (1,3), (2,3), (3,3), and (4,3), then switches, in 10 minutes, to (4,2), (4,1), and (4,0).

Professor Scarlet's (the narrator) observation is easy to show: Five people can cover every station in 50 minutes; that is, if they start from (0,0), (0,1), (0,2), (0,3), (0,4), respectively, and go down in parallel.

Reader Solutions to Mapcraft

Some smart readers "showed up" Dr. Ecco and Liane again with the Mapcraft challenge (DDJ, October 1998). The problem was to find the minimum number of population exchanges to ensure that each group constituted a connected component. I know of no algorithm to solve this problem. Nor does Ecco. So, readers who solved it did so by cleverness.

For starters, Bruce Wilson and John Porter showed that the example in the text of the puzzle could be solved in four exchanges.

(4 0) (0 1)

(0 4) (4 3)

(2 1) (0 3)

(1 1) (4 4)

producing a grid like this:

2 2 2 2 2

1 1 1 1 2

1 1 1 1 0

1 0 1 0 0

1 0 1 0 0

0 0 0 0 0

They discovered this solution by "analyzing the switches made by Liane for redundancy and for pieces that would have been okay in their starting position."

For the main puzzle, Ecco and Liane had a solution with 15 exchanges. The following clever readers found solutions with 14 exchanges:

Phil Goodwin

John Porter

Chree Haas

Michael.S.VanVertloo

Igor Pavlovic

Charles.Taylor

Ben Ziegler

Matteo Salsilli

Iulian Kakulidis

Michael Vielhaber

Some even more clever people found 13-move exchanges.

Ernst Munter

John Holland

Phil Goodwin

Nicholas Sakurai

Ralph Nebiker

Michael Scheetz

Kassim Gora

I present Ralph's solution, because it was the first I received.

   Final arrangement         Flips to achieve it

    0 1 2 3 4 5 6 7 8 9              Switches
  0 0 0 0 0 0 0 0 0 0 0             0,3   6,2

  1 2 2 2 2 0 0 0 0 0 0             2,6   9,0

  2 2 2 1 2 2 2 0 0 1 0             2,5   6,0

  3 2 2 1 1 1 2 0 1 1 0             9,1   4,5

  4 1 1 1 2 2 2 0 1 1 1             0,8   8,1

  5 1 2 1 2 2 0 0 1 1 1             0,5   9,5

  6 1 2 1 2 0 0 1 1 1 1             6,1   0,6

  7 1 2 1 2 0 0 1 1 1 1             4,7   8,3

  8 1 2 2 2 2 2 2 2 2 1             3,8   8,5

  9 1 1 1 1 1 1 1 1 1 1             2,9   8,6

                                    1,4   9,8

                                    7,4   7,8

                                    1,9   5,9
 

Finally, Steve Worley suggested the following problem: Suppose the only possible exchanges were between neighboring villages. What would the best answer be then?

DDJ