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].
Although he was two decades too old to fly fighter jets, the Air Force General Chris Warren had the confident smile and aviator glasses of a test pilot.
"We've got a base to protect and we mean to do it," he said. "Sadly, even the best guards get bored, so we need several of them. Please look at this map."
He laid a piece of paper on a table and drew a big square.
"Our base is a square 76 meters on a side on a flat desert," he said. "Our most sensitive equipment (I can't tell you what it is) will be kept in a depot underground having a surface footprint of just a few square meters. We want the guards to alert our antiterrorist team if anyone approaches the depot. I pity the poor souls who get their attention.
"We have five guard towers to put up. From each guard tower, a guard can reliably see 18 meters. But each guard isn't looking everywhere all at once, of course, so we'll want several to cover some areas near the depot. We want the guards to be able to yell to one another, but not have such easy conversation that they forget what they are doing. So, the towers should be at least six meters apart.
"We want at least 2900 square meters to be visible to one or more guards (though different square meters can be visible to different guards). At least 775 should be visible to three guards or more. (The original 2900 will include these 775, of course.) At least 100 should be visible to four or five guards."
"What does it mean for a meter to be visible? The whole meter, or just some portion?" Liane asked.
"For the purposes of this mission," the general answered, surprised by the 13-year-old's question, "assume that each guard stands in the middle of a square meter (in a tower) and that seeing another square meter means seeing the middle of that square meter.
"Your assignment is to tell me where the towers should be and tell me how many meters are visible and by how many guards. If you can do much better than my specification, I'd be grateful."
Liane and Ecco found a design to satisfy the general's desires, but weren't sure they were doing as well as possible.
Reader: See how well you can do.
Last Month's Solution
These are the groupings of front fragments (groups separated by commas): 18 11 20, 3 12 2 9, 16, 19 13, 10 6 17 8 5, 14 4 15 1 7.
These are the groupings of back fragments: 5 6, 11 16 9 17 10, 1 14, 4 13 15, 8 2, 3 7 12.
The lengths are respectively: 5.2, 11.3, 4, 7.9, 11.4, 8.1.
This is at least consistent with the ancient texts.
Reader Notes
Several clever readers matched Liane's solution to the "Beats" puzzle (DDJ, May 2001) when there were three police cars. Most of these went on to show that all five cars could follow one another in a circuit over all of the roads so some car would pass each block every 10 minutes: Richard W. Lipp, Tim Chase, Dennis Yelle, Pike Enz, Andrew D. Todd, John A. Trono, Rodney Meyer, Mike Bandy, James H. Puttick, Steve Kempf, Charles Doumar, Tyler Folsom, Craig Ewert, Paul Valckenaers, Matt Cuba, Geoffrey Probert, Jimmy Hu, Mike Ball, Steven M. Gollmer, Patrick Gaffney, Robert Murr, Mike Wilson, M. Alan Meghrigian, Dennis L. Cumro, Magne Ostlyngen, Robert Huff, Robert H. Morrison, Girts Folkmanis, Robert Bigec, Steven Augart, Denis Birnie, Wim Nuij, Mike Larsen, Norman Roundy, and Rob Holstein.
Pike Enz was the first to show that every street could be hit every 13 minutes or less by the same car. Here was his solution:
"Identifying vertices by x-y-coordinates with the origin in the lower left corner:
"1) an 8-minute circuit:
(1,4) (0,4) (0,3) (0,2) (1,2) (2,2) (2,3) (2,4)
and back to (1,4)
"2) an 8-minute circuit:
(2,2) (2,1) (1,1) (1,0) (2,0) (2,1) (3,1) (3,2)
and back to (2,2)
"3) a 9-minute circuit:
(3,1) (3,0) (4,0) (4,1) (4,2) (4,3) (3,3) (3,2) (4,2)
and back to (3,1)
"4) a 12-minute circuit:
(1,3) (2,3) (3,3) (3,4) (3,5) (3,6) (3,7) (2,7) (2,6) (1,6)
(1,5) (1,4)
and back to (1,3)
"5) a 13-minute circuit:
(2,4) (3,4) (4,4) (4,5) (4,6) (3,6) (2,6) (1,7) (1,6) (0,6)
(0,5) (1,5) (2,5)
and back to (2,4)."
DDJ
