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.

(In reply to Puzzle needs clarification: Kafka calls by ed bottemiller)

First of all, keep in mind this is not a liar or knight problem. It's a combinatorics problem. I will try to clear up any of the other problems.

==There is the "officer" and there are two groups of 10 each (colony A and colony B) called "suspects."  It is not clear whether or not the officer initially knows the "colony" of any or all of the suspects.

You are told in the second paragraph "(The officer can tell who's telling the truth.)" and you are given boxes of suspects, so you know he knows at least their identities and truthfulness. I'm not sure what else you need to know.

==There are two "identical boxes" P and Q, but no specification of in what respect they are "identical" (the sizes, shapes, etc. of the boxes do not seem relevant), except that each initially has 20 cards, "one for each suspect" (presumably not necessarily in any given ordering). Does the last clause mean that each card has only the name on one of the 20 suspects? Or are there questions to be asked the suspect(s)?   The officer after drawing a pair of cards "interrogates these two people" (could the same person's name be drawn from both boxes in one interrogation?).  Is the interrogation related to something written on these cards (the name only -- so question is "are you X"? -- or what -- e.g. "did you do it?" or "do you know who did it? or whatever)?

You can assume their shape, size, color, and such is the same, but that's not important. What is important is they have the same set of 20 cards ("The officer has two identical boxes labeled P and Q, which each have 20 cards, one for each suspect.") and thus, although he does different procedures with boxes P and Q, their initial contents are the same. It's possible he pulls the same card from both boxes, and as you might imagine, he interviews the same suspect twice.

Again, the content of the interrogation, the questions asked, and the connection between the interrogation and any possible information on the cards are not mentioned, and not important. You are given a rule for the suspects' truthfulness in paragraph 2.

==We are then told that the suspect from box P "will tell the truth" (since all 20 have their names in box P, then they will all do something truthfully: what?).  Then we are also told that the suspect from box Q "will tell the truth if and only if the suspect from box P is from colony A" . From the last we must assume that all suspects know the "colony" of each of the others, else the equivalence is meaningless -- since they must know when they should tell the truth and when they should lie.  We are told the officer "can tell who is telling the truth" -- is that from knowing the "colony" of each, or what? Truth about what?

In the statement "He interrogates these two people during the investigation; the suspect from box P will tell the truth", the intent is "telling the truth" refers to the investigation previously mentioned in that sentence.

Since all twenty suspects have their name in box P, it follows that they will all have truthful investigations, if their name is pulled out of box P.

==What is "an investigation" - each interrogation session with a pair of suspects, or each pass through the entire "boxes"? In discarding cards "from both boxes" does this mean discarding cards drawn in pairs, or finding matching names, or what??  Some "cards" (note plural) are "returned" to "the original box". 

The use of "cards" as plural versus singular is not completely clear, but since a card or cards could be returned, depending on the suspect from box Q. It's probably the intent to just mean "any cards which exist", it's possible there is a better way to phrase that.

The text does mention "Before each investigation, he takes one card from each box." "He interrogates these two people during the investigation" "After each investigation, the officer will discard cards"... so I think it's safe to assume the investigation is the interrogation of the two drawn names.

I'm not clear what "discarding in pairs" is besides finding matching names in both boxes, and that is just what he does. Any lying suspect gets his card put back; any truthful suspect gets his card discarded, from both boxes.

==We are not told what would constitute "solving the case", but are supposed to test that by a limit of 10 "investigations".  We are asked to "find the number of possibilities" of a solution: does this mean the probability of some outcome? The "number of possibilities" is TWO: he solves it, or he doesn't solve it.

The second sentence says "He can solve the case once at least 19 of them answer truthfully during an investigation." so that should be used to answer this uncertainty. Although you can state there are two possiblities, solving or not solving, this is not as detailed as the answer the author desires. The officer could draw out different names from different boxes. Each of these occurrences would mark a different possibility. Since he needs 19 truthful responses, this seems relatively low.

Posted by Gamer on 2008-08-30 23:14:17