Territory Game

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), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1997). He can be contacted at [email protected].

Dr. Jacob Ecco calls himself an omniheurist, a word that means "solver of all problems." Okay, he exagerrates a little. In fact, he solves problems of a mathematical nature, usually with practical implications ranging from cracking lovers' codes to recovering ballistic missiles. You can find the chronicles of his past adventures in a couple of books I've scribbled. He had not been allowing me to record his adventures due to his recent troubles with the National Security Agency, but he has relaxed a bit of late and I have resumed my visits to his Greenwich Village apartment, journal in hand.

There, I observe as clients come in with a problem, discuss it with Ecco, and usually leave with a solution in hand. Today's problem was different, however. Ecco wasn't satisfied with his own solution, so he asked me to resort to a computer and I'm going to ask you to do the same.

The visitor today, one Mr. Nog Tugget, came from Asteroid Mining Aerospace Satellite Systems. He gave us each a business card. "There's gold in them there asteroids," it said on the bottom.

"That's our company slogan," Tugget said with a smile. "I should add that asteroids have much more interesting metals than gold -- platinum, titanium, and minerals we've created only in labs." I looked over the gentleman. Whereas the gold rushes of the last century gave us the image of brawny, hard-drinking, and foul-mouthed prospectors, Mr. Tugget represented a new breed: an overtight tailored suit, blow-dried hair, and an acute consciousness of the present value of a mineral dollar. Remarkably, he claimed descendancy from the Alaskan gold rush itself, as I was to find out a short while later.

"The basic problem," Tugget explained, "is the nature of the deposit and the technique of exploration. We can no longer afford to explore with our sealskin boots and fishing rods the way Carmack did when his lucky discovery at Rabbit Creek turned him into a millionaire."

"He wasn't alone, as I recall," I ventured, recalling my own trip to Skagway. "There were two Tagish people with him, too, right?"

"Yeah, yeah," Tugget said impatiently. "But them Indians didn't find the gold. Carmack's dream found it. He saw a salmon with a gold nugget in its eyes lying in blue-green water. When he saw Rabbit Creek in August of 1896, he decided that was the place to pan. He and his two Indian friends took out one of the biggest loads in the history of prospecting.

"They also renamed the creek...Bonanza.

"Others came to stake claims. Most went broke or died in the harsh winter of 1897. But a few got lucky. One was my great-grandfather Deacon Tugget, though it hasn't done me much good. I trace my line through a dance hall girl whose name he didn't remember by the morning after he, well, after conception. But I'm going to achieve his greatness, by Klondike, I will."

"How can we be of service?" asked Ecco.

"Help me stake the claims," said Tugget.

"Claims?" we asked in surprise.

"Yes, it is a question of where to place our stakes," Tugget said.

"You see those third worlders at the United Nations have made a law that asteroids and planets are part of the commonwealth of mankind, so we don't have the right to just mine them at will. We must share the wealth with others -- 25 percent of our profits to those donothings.

"Besides that, the UN bureaucrats have established a law of claims. That law says that an asteroid smaller than five miles in diameter is the property of the first spacecraft that attaches to it. We will be the first to most of those, I'm sure. Our technology is far ahead of the competition. But we are after Comet Grosso, the 2000-kilometer diameter comet, and a French-Russo-Japanese consortium has the jump on us for that one.

"It's not widely known, but they have located a 100-square kilometer valley that sits on top of hundreds of billions of dollars worth of titanium and other precious metals. They call it Carré d'Or (the golden square). Carré d'Or is, in fact, nearly a perfect square, 10 kilometers on a side."

"And how is a claim established?" Ecco asked, sensing that a mathematical question was finally on its way.

"By proximity," Tugget answered, pulling out a map of the valley. It did in fact look remarkably square and flat in contrast to the rapidly rising mountains all around (Figure 1).

"Call them the red team. Suppose they land eight spacecraft and we land seven...please note that these numbers are confidential."

We nodded and he went on.

"Well, any point in the valley that is nearer to one of their spacecraft landing sites is theirs, and any point nearer to one of our landing sites is ours. If a point is equidistant, then it belongs to neither of us. That's the UN law.

"We know some things about their plans. They have divided the 100-square kilometers into a grid 1000 points on a side, in which each point is separated from its vertical and horizontal neighbors by 10 meters. That means that two ships can land on adjacent grid points."

"Do you have any idea where they'll land their ships?" Ecco asked.

Tugget smiled. "They were foolish enough to publish them. Well, sort of. Someone sent them in the clear over the Internet.

"Here are the landing points. All numbers lie between zero and 999." See Figure 2.

"So, let me get this straight," Ecco said. "They will land first, probably at these points. Your job is to find seven landing points so you can maximize the amount of the valley you own. No spacecraft is allowed to land where another one has already landed. Is that right?"

"Right," Tugget said. "If we can do better with seven than they do with eight, their investors will pour money into our stock, leaving them without the money to buy a soda pop in Circle City."

"I see that your great-grandmother had a good sense of business," Ecco said under his breath as he started making marks on the map.

A short while later, Ecco gave Tugget the map on which he had drawn several circles. "Land your spacecraft here and you can get a little over 55.6 percent of the territory whereas the other side gets only 44.3 percent with their eight spacecraft.

"And here is another set of landing points in which you get more than 51 percent of the territory with only six spacecraft, provided they land their eight at the sites you told us."

Question to readers: Can you do at least as well? I will publish the best solutions for six and seven spacecraft next month.

Tugget looked upset. "What if it's a trap?" he asked. "I mean what if they published those locations just to fool us into thinking they were doing something silly. Can we always beat them with seven spacecraft no matter which eight landing sites they choose? We still have the advantage of going after them."

Question to readers: Ecco wasn't able to solve this one on the spot. Can you? While you're at it, try the generalization: If player A can lay down n points wherever he likes and then player B can lay down n-1 points wherever he likes except on top of A's points, which can guarantee a winning strategy for each n? If you have a solution, let me know at [email protected]. If you are interested in an interactive version of this territory game, check out the Voronoi game at http://www.interport.net/~paisley/java.

DDJ