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); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); 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].
Most people knew him as the garden columnist of the main daily newspaper in Anchorage, Alaska. "But I have another identity that some of my newspaper readers may not approve of: I build gas pipelines," Alan Lionfall said. "Right now, when gas is discovered on the Alaskan north slope, it must be pumped back into the earth. I'm working on getting it into homes and power plants. Unlike oil, gas travels better underground at supercooled temperatures. The fewer the tunnels the better, especially in some of the areas precious to wildlife.
"Now, I have a bit of a mess on my hands. You see, before I got involved, previous contractors started laying some pipe through a caribou migration area. The pipes are not connecting the right areas. Some of the pipes are probably unnecessary. Those contractors are so secretive, I don't even have a map of the area. All I have are these 'leg descriptions.' I finally understand what they mean:
"The positions are described by the letters A through M. We want to send gas from B to E — that's what the contractors didn't get. Each leg is a one way pipe from one letter position to another. Here are the pipes already laid:
F E
I E
K H
G F
I K
G E
D M
L G
I E
I G
H M
J D
H M
I A
L H
G K
D A
H A
I D
J B
L J
B C
B L
Twelve-year-old Liane stopped strumming her guitar and said, "So, a leg is an edge in a graph. From what I see, there is no path from B to E."
Lionfall looked at Liane with a smile. "So, it's true she helps you solve the problems people ask of you, isn't it," he asked Ecco.
"If it weren't for child labor laws, she might put me out of business," Ecco said in a deadpan.
"In any case," Lionfall continued, "there is no path from B to E as the young guitarist says. We have a bunch of routes we could potentially use without disturbing the environment and that each cost less than $1 million. Naturally, we'd like to build as few as possible. I list the possible ones below. Which ones would you suggest we use?
K J
M I
J B
E M
H L
J K
J I
I D
E A
H C
I M
D I
G C
K L
F D
A B
H K
E F
G H
H G
E H
L M
I B
H J
E D
E B
A C
A H
G D
C J
J L
H M
E L
E J
G J
Reader: Ecco and Liane were able to get away with building only five routes. Can you match them or do better?
Last Month's Solutions
As you can see in Figure 1, Dr. Ecco's solution was based on a diagonal placement of cisterns starting at locations:
0 90 — requires 10
0 80 — requires 20
0 70 — requires 30
0 60 — requires 40
0 50 — requires 50
0 32 — requires 50
0 15 — requires 50
0 00 — requires 50
10 0 — requires 40
20 0 — requires 30
30 0 — requires 20
40 0 — requires 10
The result was about 847 cells lost with a standard deviation of 78. That was assuming the cisterns lasted for the whole season.
In Ecco's best arrangement, using the same placement, nearly 1000 burn out when each cistern holds enough water to put out only one fire.
Reader Notes
Reader responses to the Mint puzzle (DDJ, November 2000) gave me great pleasure. Not only did I see many solutions that improved on Ecco's, but several readers noted the obvious applications of a rational coinage.
Martin Brown of Belgium observed: "It might interest you to know that the Belgian currency goes 1/2, 1, 5, 20, 50, which as you can imagine, leads to pockets full of change."
Harm T. Voordenhout of the Netherlands thinks this question has continental applications: "I had been asking myself the same question for about two years. The coming of the Euro, which would replace a lot of coins in Europe, got me wondering about which system of coinage would be the best."
The following readers all improved on various aspects of Dr. Ecco's solution: Alexander Enzmann, Austin Gilbert, Jon Beal, Tomas G. Rokicki, Patrick R. Schonfeld, David Stevenson, Steve Kietzman, Martin Brown, Harm Voordenhout, Rodney Meyer, Jimmy Hu, Bruce Moskowitz, and Matt Lasley. However, the best overall solutions, in terms of completeness and original extensions, came from Ted Alper. Here are his solutions, some of which were equaled by other readers:
For three coins: If you insist on intuitive exchanges, the best average you can get is 5.3131...you can do this with denominations (1,5,22) (that is, with 1-cent, 5-cent, and 22-cent coins), but if you allow nonintuitive denominations, you can achieve 5.2020...with denominations (1,12,19). And if you allow Exchanges, you can have an average exchange number of 3.9191...with (16,19,21):
FOUR COINS:
Best intuitive average is 4.1414. Achieved with (1,3,11,37).
Best nonintuitive average is 3.9293. Achieved with (1,5,18,25).
Best exchange average is 3.1212. Achieved with (13,28,32,33).
FIVE COINS:
Best intuitive average is 3.4949. Achieved with (1,3,7,16,40).
Best nonintuitive average is 3.3232. Achieved with: (1,5,16,23,33).
Best exchange average is 2.7273. Achieved with (13,24,30,32,33).
SIX COINS:
Best intuitive average is 3.1616. Achieved with (1,2,5,11,25,62).
Best nonintuitive average is 2.9495. Achieved with (1,4,6,21,30,37).
Best exchange average is 2.5151. Achieved with (1,8,21,38,44,49).
Ted showed by comparison to the optimum possible that his solution is best: "For 6 coins, exchanging for the values 1...99: At most, 6 values can be done with only 1 coin. You can get at most (6*5)/2+6=21 different possible values with 2 coins (no exchange) and another 15 values with exchanges of size 2 (bigger-smaller). So in the best case, in which all the remaining values take 3 coins, you'll have a total number of coins required of 1*6+2*(21+15)+ 3*(99-6-21-15)=6+2*(36)+3*(57)=6+72+ 171=249, which is achieved with the coin sets I already computed."
Here were Ted's solutions when each coin was worth a multiple of 5 cents:
THREE COINS:
Best intuitive average is 2.5263. Achieved with (5,15,40).
Best nonintuitive average is 2.5263. Achieved with (5, 15,40).
Best exchange average is 2.2105. Achieved with (5,30,45).
FOUR COINS
Best intuitive average is 2.1579. Achieved with (5,10,25,60).
Best nonintuitive average is 2.1053. Achieved with (5,10,30,45).
Best exchange average is 1.8947. Achieved with (10,25,65,70).
FIVE COINS
Best intuitive Average is 1.9474. Achieved with (5,10,15,30,65).
Best nonintuitive Average is 1.8421. Achieved with (5,15,25,30,65).
Best exchange average is 1.7368. Achieved with (5,10,15,45,80).
DDJ
