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.
It seems we are only interested in the combinations where at most there is one draw from box P of a suspect from Colony B, as any more than one draw from box P of a suspect from Colony B will result in at least two untruthful suspect interrogations.
We need 19 truthful suspects in 10 draws in order for the case to be solved in 10 draws (any additional draws from box P of Colony B suspects will result in a failure to do so). The matter of replacement of untruthful suspects drawn from box Q seems it will have no effect on the outcome of this solution, and, thus can be considered a red herring.
There are [2
^{10}] combinations where all ten draws from box P are suspects from Colony A. There are [10 x 2
^{10}] combinations where only one of each of the ten draws from box P are suspects from Colony B.
Thus, there are
a total of [11 x 2^{10 }= 11264] combinatorial possibilities where the case will be solved in ten draws.

Posted by Dej Mar
on 20080901 03:06:14 