Dennis, a professor of computer science at New York University and author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), can be contacted at [email protected].
He claimed to be a military man, but Captain Solo didn't seem to have the right bearing. He slumped in one chair with his feet propped on another. His uniform was clean, but badly wrinkled. His hair was unkempt. In brief, he looked like one of my colleagues.
His smartly dressed assistant, Lieutenant Hood, presented the problem to Ecco. "Here is the layout of the valley, sir," he said.
"Our hovertanks will be approaching from the eastern pass. When our adversaries detect us, they will approach from the western pass.
"Our job is to destroy the underground factories in the valley. The factories themselves have no defenses except their one-meter-thick walls, but we must quickly dominate the ground above. That means we must rapidly reach a situation in which we can destroy any new vehicle that comes into the valley."
"Why can't you just cross over with your first hovertank and block their pass?" Liane asked.
"They have field guns and rocket-propelled explosives inside bunkers overlooking the western pass," the lieutenant responded. "We have, however, located 25 hills that are good vantage points for our hovertanks. Occupying any 10 of them will allow us to destroy the underground factories. We just want to be safe on them while keeping our adversaries to under five."
"So, drive to the first 10 hills you can see," Ecco said with some impatience.
Solo spoke up. "We wouldn't be here if it were that simple, Dr. Ecco. You must think of this as a two-person game with alternating moves. We place a vehicle, then they place one. Then we place one. Then they do. And so on. We just want to be sure that after they have placed five, they can't place any more, whereas we can place at least 10 altogether."
"Can you get to any hill equally fast?" Liane asked.
Solo nodded. "I designed every hovertank to fly at 80 miles an hour and to stop on a dime."
"Unfortunately, our adversaries have access to the same technology," added the lieutenant.
"Our biggest advantage is that we will be in the valley first. In fact, we hope that we will be able to place at least two and possibly three hovertanks on hills in the valley before they place any of theirs. After that, we will alternate. Remember, we want to prevent them from placing more than five of their hovertanks and we want to be able to place at least 10 of ours. Also, our 10 hovertanks must be able to fire upon all unoccupied hills. Finally, their five hovertanks must not be able to fire upon our 10."
"Can you tell me which hills can fire upon which others?" Ecco asked.
"Yes," the lieutenant responded, handing Ecco the table below (also available electronically, see "Resource Center," page 3). "We've numbered the hills from 0 to 24. I hope the table is clear. For example, hill 0 can fire upon hills 1 2 3 7 9 8 13 17 18 19 20 22 24. Note that firing is usually but not always symmetric. For example, 0 can fire upon 2 but the reverse does not hold."
Fire From Fire Upon 0 1 2 3 7 9 8 13 17 18 19 20 22 24 1 0 2 3 9 10 13 14 15 16 17 20 21 24 2 3 5 9 11 12 13 16 22 23 3 2 5 7 9 11 12 13 16 22 4 5 7 9 11 12 13 16 22 23 5 2 3 4 7 9 11 12 23 6 1 2 3 7 9 8 13 14 15 16 18 20 21 7 3 4 5 9 12 19 20 22 23 8 0 6 10 14 15 17 18 19 24 9 2 3 4 5 7 11 19 20 22 10 1 2 3 7 8 9 13 15 16 20 21 22 24 11 2 3 4 5 9 19 20 22 23 12 2 3 4 5 7 8 17 18 23 13 0 1 2 3 6 7 9 10 16 18 21 22 24 14 1 6 8 15 16 17 18 19 21 22 24 15 1 2 3 6 8 10 14 16 18 19 20 22 16 1 2 3 4 7 6 9 10 13 14 15 17 19 22 17 0 1 8 14 16 18 20 21 24 18 0 6 8 13 14 15 17 21 22 19 0 8 14 15 16 20 21 22 24 20 0 1 2 3 6 9 10 15 17 19 22 24 21 1 6 10 13 14 17 18 19 24 22 0 10 13 14 15 16 18 19 20 23 2 4 5 7 11 12 19 20 22 24 0 1 8 10 13 14 15 17 19 20 21
Ecco and Liane studied the table for a while. Suddenly, Liane giggled and said, "Two sets of queens problems." She then sketched something on paper that looked like two squares and showed it to Ecco who nodded.
Ecco then turned to us and stifled a yawn. "Gentlemen, let me take a three, four, or five minute nap, and then I'll get back to you."
When Ecco returned, he handed Captain Solo a piece of paper. "If you can place three hovertanks before your adversaries can place any, then take these three and you can prevent the adversary from occupying any hills, because your hovertanks will be able to fire upon every remaining hill. If you can place only two before they can place any, then choose these two. You will be able to keep the adversaries to under five, occupy 10 yourself, and be able to fire upon all remaining hills. If you can place only one before they can place any, then I don't think you can achieve your goals, but I'm not sure and, well, you haven't asked."
Reader: Please show Solo how (a) he can dominate the valley entirely by occupying three hills before his adversaries can occupy any; and (b) he can achieve the conditions of the problem by occupying two hills before his adversaries can occupy any (and alternating thereafter). If you have a proof either way concerning the last problem (if the adversaries allow Solo only one hill before alternating moves begins), then send it to me at [email protected].
Last Month's Solution
Since each accusation must include at least one lying informant and all two accusation pairs below are disjoint, there have to be at least six:
Accuser Accused petra gwenyth sam larry dave mike isaac nick hillary kris olivia ulm
If the following eight people have been turned, they suffice to explain all the accusations that commissioner Bratt has presented to Ecco: isaac hillary larry olivia gwenyth dave sam petra. Ecco doesn't know whether this is the minimum possible.
Superheurists: DDJ readers Gary Knowles, Jon Beal, and Kent Donaldson all found clever solutions to the May 1998 Nimmerics problem. Kent also has the best solution so far to the Territory Game in which his first six ships get 66.60 percent of the valley and all seven get 73.83 percent.
DDJ
Copyright © 1998, Dr. Dobb's Journal
