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). He can be contacted at [email protected].
The police commissioner explained, "We're trying to crack a major drug cartel." Commissioner Bratt is well known for his work in bringing down New York crime. It's less well known that he has been a frequent visitor to Ecco's apartment over the years. "We're using informants, but these guys are rewarded for their information, so they tend to, well, dissemble."
"That means 'lie,' doesn't it?" Liane asked with a smile.
"Well, yes, young lady," Bratt said after a brief pause, "but these are the best we could get. This cartel is one of the smoothest and smartest we've ever seen. It's run out of Argentina, with offices all over Bolivia.
"You've met the chief, Ecco, I think," Bratt continued. "The professor here talked about Solaris (also known as El Jefito, because of his diminutive size) in his monograph Codes, Puzzles, and Conspiracy. You met him at the Casino in Punta del Este. You never figured out his role in Baskerhound's escapades, unfortunately."
"Ah yes, the Rhodes Scholar wrestler with a weakness for bimbos," Ecco said with a smile.
"Right. Especially ones wearing tight-fitting clothes," the Commissioner responded. "Some of those beauties figure among our informants."
"Well, how many informants are there altogether?" Ecco asked.
"Twenty," said the commissioner. "I think he has turned some of them, but not most, I hope. The result, however, is that now we have some informants calling other ones liars. We don't know whom to trust.
"The thing is, we have vetted these informants quite carefully, so we think that not more than five have turned, though it may be as many as eight," Bratt said.
"So, you know neither who lies, nor how many?" asked Liane in a slightly mocking tone.
Bratt glared at her, but nodded. "That's right. It could be any of them."
"Can you tell us who accuses whom?" Ecco asked.
Bratt laid out a list (changing the names for obvious reasons):
Accuser Accused petra gwenyth sam larry hillary petra olivia petra gwenyth alan dave mike isaac nick hillary kris sam jack sam rivera gwenyth mike olivia ulm jack larry jack sam alan larry isaac mike hillary ulm ulm larry gwenyth jack gwenyth olivia olivia kris larry mike tom hillary emily isaac petra rivera mike larry dave ulm hillary bob larry hillary gwenyth kris
"Well, Liane," Ecco said. "What do you make of the situation?"
"I need some more clarification," she replied. "Commissioner Bratt, am I correct in drawing the following inferences?
"Suppose X accuses Y of lying:
- At least one is a liar.
- If we know that X tells the truth, then Y is a liar.
- If we know that Y tells the truth, then X is a liar.
- If X lies, then his accusations may or may not be true."
"Absolutely our thinking," said the commissioner, visibly impressed. "The last point is particularly important. Lying informants may still point the finger at other liars. Also, we don't fault truth-tellers for failing to accuse liars. They simply may not know enough."
"And our job," Liane went on, "is to find the smallest set of liars that explain all these accusations?"
"Right again," Bratt said, as he glanced anxiously at Ecco.
Ecco nibbled at a scone and stared at the list. Liane doodled while she looked at it.
After a few minutes, Ecco wrote eight names on a postit and handed it to the commissioner. "Here are a set of eight liars who could explain all these accusations. Liane, did I make a mistake? Can you solve the problem with fewer liars?"
"I'm not sure," Liane said. "There have to be at least six though."
Reader, your puzzle: First, why do there have to be at least six? Second, are eight liars a sufficient number to explain all these accusations? If so, which eight? Could there be fewer? If so, who would they be? Let me know at [email protected].
Last Month's Solution
X=30, Y=43. This is hard to solve in closed form. I used game tree analysis in my favorite programming language, K. If there are twice as many bills in the container, then X=29 and Y=41.
For Expanding Nim, notice that four and five are both Win2 numbers since the second player can remove the last stone no matter how many the first player removes in his turn.
For example, if there are five and the first player removes one stone, then the second can remove four stones. Similarly, 10, 11, and 12 are all Win2 numbers, since the second player can force a situation in which the first player is left with either six or seven stones at his second move. For example, if there are 10 stones to begin with and the first player removes three, then the second player removes one and the first player is faced with six. Since the first player at this point can take only five, the second player will win.
So, the following are all Win2 numbers:
{4,5} (that is, 4 or 5);
{4,5}+{6,7} (that is, 10, 11, or 12, which are the sum of 4+6, 5+6 (or 4+7), and 5+7, respectively);
{4,5}+{6,7}+{8,9} (that is, 18 through 21);
{4,5}+{6,7}+{8,9}+{10,11} (that is, 28 through 32);
{4,5}+{6,7}+{8,9}+{10,11}+{12,13} (that is, 40 through 45);
{4,5}+{6,7}+{8,9}+{10,11}+{12,13}+{14,15} (that is, 54 through 60);
{4,5}+{6,7}+{8,9}+{10,11}+{12,13}+{14,15}+{16,17} (that is, 70 through 77).
Liane's answer is 59, 60, and 70.
The winning strategy for the second player goes like this for, say, 71. In the first two moves, force the number down to {6,7}+{8,9}+{10,11}+{12,13}+{14,15}+{16,17}, that is, 66 (taking the sum of the minimum of each pair) through 72 (taking the sum of the maximum of each pair). In the second two moves, force the number down to {8,9}+{10,11}+{12,13}+{14,15}+ {16,17}, that is, 60 through 65. Then 52 through 56, 42 through 45, 30 through 32, 16, or 17, then 0.
Reader Solutions to the Territory Game
As of the midMarch deadline for this column, I've received many clever solutions from readers regarding the Territory Game (DDJ, April, 1998). Dr. Ecco's symmetric solution did the job, but was far from optimal. (Dr. Ecco wanted Tugget out of his apartment as soon as possible.) The best solution I have received came from David Weiblen. His first six ships get 66.3 percent of the territory, and all seven get 73.5 percent:
Ship 1 375 212
Ship 2 507 293
Ship 3 585 461
Ship 4 819 743
Ship 5 205 563
Ship 6 817 743
Ship 7 415 901
Nearly as good solutions came in from Jon Beal, Albert H. Behnke, Martin Brown, Bob Byard, Matte Kalinowski, Gary Knowles, Scott Starsman, Michael Van Vertloo, and Michael Williams.
Both Weiblen and Brown observed that just four ships suffice to give more than 50 percent of the territory. Here is Brown's landing selection:.
Ship 1 630 298
Ship 2 375 212
Ship 3 817 745
Ship 4 205 563
Several readers suggested heuristics for winning the game in general. Most were of the form: Try to spread your ships as evenly as possible. This does not quite an algorithm (or a proof) make, but it certainly sounds like a promising approach. The solution to these territory games (or Voronoi games, as I've called them in my more academic moments) might someday make a nice article in the American Mathematical Monthly. Don't forget the interactive version at http://www.interport.net/~paisley/java/.
DDJ
Copyright © 1998, Dr. Dobb's Journal
