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].
Why would a military man be asking about sprinklers? General Warren gave only a hint of an explanation.
"You gave us outstanding service in designing the watchtowers around our airbase," he said. "I was hoping you could help us out here too. The mathematics may even be similar. Imagine that you have an experimental farm in the Sonoran desert. The farm is a rectangle 20x30 meters on a side. Your five sprinklers can each water a circular area having a radius up to 12 meters. We want to water as much of the 600 square meters of the farm as possible, but we have some constraints.
"You see, there are certain cactus plants of the rare California Barrel variety that we want to preserve. Right now there are 11 inside the rectangle, each occupying one of the square meters, and we want to preserve at least 10 of them. That is, no water should touch at least 10 of the 11 cacti. Furthermore, no water should leave the rectangle of the farm. Each sprinkler can water any radius up to 12 meters, though you can adjust that amount down if you wish.
"Your mission is to place the sprinklers in the center of certain square meters and to adjust the length of each of their sprays, in order to touch as many square meters as possible (without wetting more than one cactus). The sprinkler touches a square meter if its water hits the center of that square meter."
"Nice problem," 13-year-old Liane said, having half-listened while on the phone and responding to three instant messages. "But you haven't told us where the cacti are."
"Correct," the General said. "Here are (starting at location (0,0) as I know you prefer) the California Barrel cacti:
3 13
13 16
3 7
10 11
10 15
20 15
26 3
9 16
11 9
27 4
4 9
Reader: Liane was able to place the sprinklers in such a way as to cover 361 square meters while sparing 10 of the 11 cacti. Ecco thinks someone can do better. Would you like to give it a try?
The General studied the solution. "I was hoping we'd do better, but since our own experts couldn't create a design that would cover more than 340 square meters, my visit has certainly not been in vain. Many thanks." He left with a half salute.
"Liane, nice work," Ecco said. "How many square meters could you cover if watering outside the rectangle were allowed, but 10 cacti inside the rectangle still had to be preserved?"
I never heard the answer.
Reader: Would you like to give it a try?
Last Month's Solution
Here's one approach to last month's "Ultimate Tic-Tac-Toe" puzzle: Define a corner to be the three perimeter cells nearest a corner. X must have two out of three cells in at least one corner, since there are only six Os in the entire perimeter (see Figure 1). X can force a win by choosing a corner in which X has a majority and placing an X just inside that corner. This creates two possibilities for X to win a threesome in the final move.
Reader Notes
Several readers found solutions to "Child's Ply" (DDJ, October 2001) that covered all 81 squares by cycling between the following two constraints:
1. odd or divisible by 3
2. even
Michael Birken was the first to do so:
81 72 left 72 64 63 left+down 54 48 56 42 40 45 36 27 18 9 8 7 16 24 32 35
28 24 up 30 36 42 right 49 56 right 63 54 48 40 45 36 27 24 18 8 9 16 7 6 12
14 21 32 35 30 24 28 18 20 25 20 left 18 14 21 12 6 10 5 4 3 2 1 2 right 3 4
right 5 10 15 12 left 12 16 15 left+down 8 6 4 up 6 8 9
Others who solved the first problem included Tomas G. Rokicki, David Berson, Rodney Meyer, Steve Kietzman, Rick Kaye, Andrew Palfreyman, Burghart Hoffrichter, and Alexander Fedorov.
Rodney Meyer showed that the constraints:
1. even
2. odd or has 2
can also cover the whole board in one turn.
Birken went on to show that 12 turns were sufficient to cover all 81 squares, each exactly once, using the rules:
1. even
2. odd
3. divisible by 3
He assumed that each turn started with the even constraint. That is, so far, the reigning solution for rules without combinations. You'll note, though, the number of turns with only one square chosen.
1. 8 (row=1, column=8) 9 18 24 27 36 40 45 54 56 63 48 42 49 36 42 down 35 48 56 63 54 40 45 36 32 27 18 24 21 24 right+up 30 25 30 right 28 35 24 18 21 12 14 7 6 10 15 12 left 8 3 6 4 left 9 12 down 8 3 6 4 left+down 5 6 14 7 12 10 15 18 28
2. 4 (row=1, column=4) 5
3. 2 (row=1, column=2) 1
4. 72 (row=8, column=9) 81 72 left 64
5. 16 (row=8, column=2) 9
6. 16 (row=2, column=8)
7. 2 (row=2, column=1)
8. 32 (row=4, column=8)
9. 20 (row=4, column=5)
10. 16 (row=4, column=4)
11. 20 (row=5, column=4)
12. 8 (row=8, column=1)
DDJ
