Dennis is a professor of computer science at the Courant Institute, New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at [email protected].
Solution to January 2005 Dr. Ecco
Saturday afternoon in Ecco's MacDougal Street apartment: Tyler and Liane were comparing strategies for the Voronoi game. Ecco and I discussed connections between monster groups and string theory.
"The math is pretty," Ecco said after a while. "My current avocation is to work out an experimental design to see whether a rapidly pulsed energy source could give evidence of those high-dimensional vibrational strings..." We all have our hobbies.
The buzzer rang. Ecco looked out from his second-floor window. "Some official visitors," he said not altogether approvingly. He collected his papers and put them into a large envelope—his filing system.
"Children," he said to Liane and Tyler, "our spook friends are back." Liane found a pad. She gave a sheet to Tyler. He started to doodle.
Our four visitors all wore suits. Three took out a kind of wand and scanned the room. The other one, evidently in authority, sat and watched. The three nodded and stood behind the seated figure.
"My code name is Purple," the seated man said. "I will tell you only the details you have to know. We need to resolve this problem in the next 20 minutes if possible.
"Imagine a road grid with seven rows as in Figure 1. Some bad guys have placed a tunnel from the bottom, beginning at the road marked Start, to the top at End. The tunnel follows the roads somehow but may wind around. It is also a simple path (no dead ends and no loops along the way). You want to probe a minimum number of times and yet be able to find the exact route of the tunnel.
"A probe device takes an hour to set up. If you set up a probe on a street, you can tell whether it follows the street. If you set it up on an intersection, you can tell whether the tunnel passes through the intersection, and if so, which adjacent streets it goes to.
"If the tunnel is at most eight blocks long and starts at Start and ends at End, then what is the minimum number of probe devices you would need to guarantee determining the precise route of the tunnel in one hour?
"Also, if you had only one probe, what is the minimum time it would take to guarantee determining the outcome?"
Ecco, Liane, and Tyler conferred for a while. Finally, they sketched an answer. Mr. Purple studied it.
"I can't thank you enough," he said. "I think this is exactly what I need, though I'm not completely sure. The tunnel might be 10 or even 12 blocks long. We don't think so, but we can't rule it out.
"Can you answer the above two questions if the tunnel could be 10 blocks or 12 blocks long?"
I left before Ecco and his talented family could find an answer.
DDJ
