wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Unreliable Witnesses
        
(Message started by: THUDandBLUNDER on Oct 16th, 2004, 11:21pm)
Title: Unreliable Witnesses
Post by THUDandBLUNDER on Oct 16th, 2004, 11:21pm
The Drugs Squad are prosecuting 10 suspected drugs dealers and have 5 witnesses whom they don't completely trust.
For each suspect, the 5 witnesses are asked whether or not they saw the suspect sell drugs.

SUSPECT                SOLD                                DIDN'T SELL
                                                                                       DRUGS                            DRUGS  

1                                                                                                              5                                                    0

2                                                                                                              0                                                    5

3                                                                                                              2                                                    3

4                                                                                                              5                                                    0

5                                                                                                              4                                                    1

6                                                                                                              0                                                    5

7                                                                                                              3                                                    2

8                                                                                                              5                                                    0

9                                                                                                              0                                                    5

10                                                                                                            1                                                    4



A) What is the fewest number of lies that can possibly have been told?

B) Given only that the total number of lies told by all of the witnesses is exactly 9, and that most of the lies claim 'sold no drugs' when the truth is 'sold drugs', which suspects actually sold drugs?
Title: Re: Unreliable Witnesses
Post by towr on Oct 17th, 2004, 8:16am
The answer to A is 0. Not every witness needs to have seen everything (which is what was asked).
Title: Re: Unreliable Witnesses
Post by THUDandBLUNDER on Oct 17th, 2004, 9:40am

on 10/17/04 at 08:16:54, towr wrote:
The answer to A is 0. Not every witness needs to have seen everything (which is what was asked).

A) asks the for the minimum possible number of lies that were told in total about all of the suspects by all of the witnesses.

Title: Re: Unreliable Witnesses
Post by TenaliRaman on Oct 17th, 2004, 11:38am
::[hide]
A> 6
B> Suspects 1,5,7,8,10 sold drugs
[/hide]::
Title: Re: Unreliable Witnesses
Post by THUDandBLUNDER on Oct 17th, 2004, 11:57am

Quote:
A> 6

:[hide]Nope, A [smiley=ngtr.gif] 6  [/hide] :P


Quote:
B> Suspects 1,5,7,8,10 sold drugs ::

:[hide]So they were all lying about Suspect 4?[/hide]

Method?
Title: Re: Unreliable Witnesses
Post by TenaliRaman on Oct 17th, 2004, 1:42pm
Oops yes i walked right over 4 ....

::[hide]
As for the method,
i made 2 assumptions
1> every witness knows everything abt every suspect
2> at any instant all the witnesses don't lie

the implications of these two assumptions are direct ...
any row that has (sold,not sold) = (5,0) or (0,5) is out of suspicion.

All other rows were under suspicion

for a, i just added the mins of (sold,not sold)

for b, i first looked at the not sold column
and added all those values which were <5
that adds to 10
but we are looking for 9

a bit of trial and error as to what combo of sold/not sold gives 9 leads to the solution ....
[/hide]::
Title: Re: Unreliable Witnesses
Post by THUDandBLUNDER on Oct 17th, 2004, 6:24pm

Quote:
a bit of trial and error as to what combo of sold/not sold gives 9 leads to the solution .... ::

Trial and error? But are you sure that is an appropriate method to use in a criminal case like this?  :P
Title: Re: Unreliable Witnesses
Post by towr on Oct 18th, 2004, 12:24am

on 10/17/04 at 09:40:09, THUDandBLUNDER wrote:
A) asks the for the minimum possible number of lies that were told in total about all of the suspects by all of the witnesses.
I don't know what you call a lie, but if someone didn't see something, and he says he didn't see it, I wouldn't call that a lie..

If you want the minimum possible number of mistaken inferences about who sold drugs, that's 6, the sum of the minimum(pro, con) of for each suspect. But none of those accounts need to be lies.
Title: Re: Unreliable Witnesses
Post by THUDandBLUNDER on Oct 18th, 2004, 4:33am

Quote:
don't know what you call a lie, but if someone didn't see something, and he says he didn't see it, I wouldn't call that a lie..

I suppose you mean that, just as seeing is believing, not seeing is not believing.  :D

But, if one assumes your interpretation of the problem,
A) is trivial
and
B) is insoluble

Next puzzle, please!
Title: Re: Unreliable Witnesses
Post by Three Hands on Oct 18th, 2004, 5:54am
Well, for A, either Towr is correct in his statement, or (assuming that all witnesses have seen all the suspects a sufficient number of times to have equivalent to full information) the fewest number of lies would be 6.

For B, all I could say is that, given that most of the lies told were saying "Didn't Sell" when it should be "Sold", there is at least one witness for Suspects 1, 4 and 8 - presumably sufficient evidence for the Drugs Squad. For all the others, they are possible sellers, but I can't be bothered to work out all the different possibilities now.
Title: Re: Unreliable Witnesses
Post by Keith H on Apr 5th, 2005, 3:13pm
Well, nobody has provided any explanation for this old problem, so I shall. The answer is already in the clear on this thread so I won't hide it.

Suspects 3,5,7, and 10 are under consideration. Suspect 3 contributes either 2 or 3 lies, which I'll rewrite as contributing {2,3} lies (order is insignificant in this notation). Suspect 5 contributes {1,4} lies. Suspect 7 contributes {2,3} lies, and suspect 10 contributes {1,4} lies. Thus, if we just look at suspects 3 and 5 (call this group A), they contribute a total of {3,4,6,7} lies ({2+1,3+1,2+4,3+4}). Similarly suspects 7 and 10 (group B) contribute {3,4,6,7} lies.

We know that all four suspects together contribute 9 lies, and that only happens in two situations: group A contributes 6 lies and group B contributes 3, or A contributes 3 and B contributes 6.

Examining both cases (trace back to where the 6's and 3's came from), we see that in the first case, the breakdown of lies is 7 false positives (regarding suspects 3, 5, and 10) and 2 false negatives (regarding suspect 7). That contradicts the assumption that false negatives were more common. A quick symmetric check shows that in the second case, 7 false negatives and 2 false positives occur.

Thus the only solution is when group A contributes 3 lies (3 is not guilty, 5 is guilty) and both members of group B are guilty (for 6 group B lies). In other words, of the four suspects under consideration, 5, 7, and 10 are guilty.
Title: Re: Unreliable Witnesses
Post by Deedlit on Apr 6th, 2005, 4:46pm
Well, we aren't given that the remaining suspects aren't under consideration.  So you're about one line from a complete proof.  ;)
Title: Re: Unreliable Witnesses
Post by Keith H on Apr 12th, 2005, 2:13pm

on 04/06/05 at 16:46:27, Deedlit wrote:
Well, we aren't given that the remaining suspects aren't under consideration.  So you're about one line from a complete proof.  ;)

I was just filling in the "trial and error" gap from an earlier proof, so I left out the obvious fact that there are too many contradicting testimonies to allow one of the (0,5) or (5,0) suspects to be incorrectly identified.
Title: Re: Unreliable Witnesses
Post by Deedlit on Apr 13th, 2005, 8:31pm
Fair enough.  :D


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board