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].
Sometimes, art imitates life. Joseph Conrad might smile at this particular imitation.
Ecco's visitor introduced himself as Austerlitz Toulemonde. "I am from the Napoleonic Society," he explained. "We use swords and firearms from the time of the Emperor. When it comes to small arms, we prefer Gribeauval pistols, ideally the 1806 models. When disagreements arise, we encourage duels, though only to the first touché. Also, our vests are made of kevlar. Even when we're wounded, no one is too badly hurt. Our members prefer modern surgeons to barbers.
"Now it happens that I have been caught in flagrant delit with the extremely charming wife of another member. To protect his honor, he has slapped me with his glove and we must duel tomorrow. In this duel, I am the challenged and he is the challenger.
"The basic duel scenario of our society is that there are two duelists. They start by standing 100 paces apart. The challenged has three bullets and the challenger has two.
"At 100 paces, the duelists have no chance of hitting one another, and duelist 1 has the option to shoot first. If duelist 1 shoots and misses or declines to shoot, then duelist 2 may choose to shoot. If duelist 2 shoots and misses or declines to shoot, then they advance towards one another by five paces each (10 paces together). At that point, each duelist takes his turn, first duelist 1 and then duelist 2. This continues as long as there are bullets in the guns. According to our society's rules, duelist 1 is always the challenger. I have the advantage of the extra bullet, however.
"The probability of hitting your opponent (and therefore winning) with a given bullet at distance d is (100-d)/100. So, at 100 paces, the probability is 0. At 0 paces, the probability is 1.
"My question to you is: What are my chances of winning, assuming neither of us can quit in the middle of the duel?"
"Well, if you as the challenged have one bullet left and the challenger has at least one, then you should shoot at 50 paces," Liane volunteered quickly. "If the challenger has no bullets left and you have one at 50 paces, you should hold your fire."
Reader: Before reading on, is Liane suggesting the impetuous?
Ecco smiled at his 13-year-old niece. "Would you like to explain?"
"Yes. At 50 paces, the challenged has a 0.5 chance of winning. If he misses, he will surely lose, but at least he has the 0.5 chance. Now, if the challenged decides not to shoot, then the challenger could win with a probability of 0.6 at 40 paces. Of course, if the challenger has no bullets left, then the challenged should wait until he is 0 paces away from the challenger to shoot." Liane answered with her customary self confidence.
Toulemonde nodded at Liane's answer. "Nicely done, belle fille," he said. "But I need to know what to do with my three bullets against his two, starting at 100 paces."
Ecco and Liane worked out the problem using a technique that Liane had recently picked up from her algorithms book Dynamic Programming. They concluded that Austerlitz would usually win. Can you tell by how much?
Reader: What if both started out with three bullets?
Last Month's Solution
To answer the general's original question in which no sprinkler should hit an area outside the farm and 10 of the 11 rare cacti should be spared, here are good places to put the sprinklers.
sprinkler 1: 11 2 range: 2
sprinkler 2: 3 3 range: 3
sprinkler 3: 8 7 range: 3.37
sprinkler 4: 20 10 range: 9
sprinkler 6: 6 15 range: 3
This covers 361 square meters with the following covering map, where 9s represent cacti that we spare and the 8 represents a cactus we water:
00020000000000000000
02222200000000000000
02222200000000000000
22222229000009050000
02222200090005555500
02222233300005555500
00020333330055555550
00003333333005555500
00003333333005555500
00103333333000059000
01110333330900090000
11111033394000000000
01110044444444400000
00100444444444449000
00004444444444444000
00044444444444444400
00444444444444444440
00444444444444444440
00444444444444444440
00444444444444444440
04444444444444484444
00444444444444444440
00444444444444444440
00444444444444444440
00444444444444444440
00044444444444444400
00094444444444444000
00009444444444440000
00000044444444400000
00000000004000000000
Reader Notes
Several readers improved on Liane's solution to the "Sprawl" problem (DDJ, November 2001). These included Michael Birken, Aaron R. Coleman, Alexander Fedorov, Andrew Palfreyman, Tim Chase, Stephen Waits, and Andrew Calafato.
Calafato and Waits suggested putting the parks at these locations (2,3), (2,4), (4,3), (4,4), and (8,8), giving two of the first owners very pleasant vistas and retarding full development for 17 years. This gives an initial configuration of:
000000000000
000000000000
000PP0000000
000110000000
000PP0000000
000000000000
000000000000
000000000000
00000000P100
000000000100
000000000000
000000000000
Calafato described his approach as follows: "The heuristic I used was: Cover up the most central building so that no development will take place from the center. Then place the last park near the other developed pair, and place it towards the center (at (8,8)) so that construction has to go around it, taking a bit more time."
Birken found a solution that could retard sprawl indefinitely on 15 nonpark parcels starting with parks at: (3,8), (4,9), (4,10), (1,7), (2,7). That gives a final configuration of:
111111110000
1111111P0000
1111111P0000
11111111P000
111111111PP1
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
Andrew Palfreyman used an exhaustive search approach to show that if the Sprawler moves second, he can guarantee to cover all nonpark land in 11 years.
DDJ
