Dennis is a professor of computer science at New York University. His most recent books are Dr. Ecco's Cyberpuzzles (2002) and Puzzling Adventures (2005), both published by W.W. Norton. He can be contacted at [email protected].
Solution to Last Month's Dr. Ecco
Michael Sturm handed Ecco his business card. The listed profession: Geometer-Farmer. "I'm a rather unusual farmer," he said after noting Ecco's smile. "My passions in fact are geometry and mechanics. I have designed sprinklers that can move around a radius of up to 1.5 kilometers for example. The farmer part is familial. My brother and I have just bought a rectangular property that is 1 kilometer north-south by 2 kilometers east-west.
"We want to water all of our land without watering too much area twice and without watering outside our rectangles. So, we measure cost (or overhead, if you wish) as the area outside the square that receives water and the area within the square having more than one sprinkler circle covering it. We want to minimize cost while ensuring that every bit of our farm is watered."
Liane interrupted briefly: "So if some area gets hit by three sprinklers, then you count that the same as if it were hit by just two?"
"Yes, good question," said Sturm shaking Liane's hand. "Not everyone picks up that subtle point. Now here are my questions. For k=5:
- What is the radius of k circles that will cover the entire rectangle while minimizing cost?
- Answer the same question if all the sprinkler radiuses must be the same."
Sturm went on, but Tyler and Liane could not solve the next questions. So these are still open:
- How do your answers change as k increases, say, to 10, 20, and 100?
- For a given k, what is the rectangle whose aspect ratio would be best and that would allow one to cover the rectangle at minimum cost?
Reader Solutions To "Dig That!"
Michael Birken and Rick Kaye came up with several very clever solutions to the "Dig That!" puzzle (DDJ, February 2005).
The problem was to find the route of an underground tunnel using probes at the intersection of a road grid. Each probe could determine the entering and leaving directions of the tunnel if the tunnel were present. Mike's five-probe solution for a tunnel of length 8 is available at http://cs.nyu.edu/cs/faculty/shasha/papers/digthat8.PNG. For tunnels of lengths 10 and 12, he came up with 8 and 15 probe solutions, though he is not sure of optimality.
DDJ