Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Beautiful Liars


Dr. Ecco's Omniheurist Corner

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):

AccuserAccused
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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.