An officer has to solve a case with 20 suspects, 10 from colony A, and 10 from colony B. He can solve the case once at least 19 of them answer truthfully during an investigation.

The officer has two identical boxes labeled P and Q, which each have 20 cards, one for each suspect. Before each investigation, he takes one card from each box. He interrogates these two people during the investigation; the suspect from box P will tell the truth, and the suspect from box Q will tell the truth if and only if the suspect from box P is from colony A. (The officer can tell who's telling the truth.)

After each investigation, the officer will discard cards from truthful suspects (from both boxes) and return cards from lying suspects to the original box.

Find the number of possibilities that he can solve the case in 10 investigations.

The wording of the problem does leave some question open regarding the procedure. 

The officer takes one card from each box implies that the two cards may be for the same suspect.
The officer interrogates these two people implies the cards taken must be two different suspects.

Can you confirm whether the cards may be for the same suspect or must each card drawn be for different suspects? If they can be for the same suspect, does answering the truth during the first half of the interrogation and not doing so in the second half of the same interrogation fall under the category of having answered truthfully?

In addition, what defines an "investigation"? In my initial analysis of this problem, I was making the assumption that an "investigation" was comprised of two interrogations -- one suspect from each box. Yet, the statement that after each investigation the officer will return cards from lying suspects to the original box indicates it may be otherwise, as only the suspect(s) from box Q may lie. And, for the condition that there be plural liars in a single investigation, there would have to be more than a single set of two interrogations.

Edited on August 30, 2008, 8:17 am

Posted by Dej Mar on 2008-08-29 22:30:20