permaculture playing cards*
The moose likes Meaningless Drivel and the fly likes Puzzle Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Puzzle" Watch "Puzzle" New topic
Author

Puzzle

Aj Mathia
Ranch Hand

Joined: Apr 11, 2003
Posts: 478
Originally posted by fred Joly:
Thank you both for your replies.
Yes the "bit pattern" is really clever and yet so "simple".
Now I was wondering what can we do if we know that some bottle(maybe none) are poisened and not just one.
The bit pattern does not work anymore.
How many prisonners do we need?

PS : as i understand most of you are asleep by now.
Here (France) it's about 9 AM. So when you wake up, maybe I will
have come up with a solution....I let you know


100 prisoners


You think you know me .... You will never know me ... You know only what I let you know ... You are just a puppet ... --CMG
fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
I guess it is more complicated than that.
For exemple with 4 bottles , I need only 3 prisonners.
Now i'm trying to extract a method from that.

Let's say 4 bottles B1, B2, B3, B4 and 3 prisonners P1, P2, P3

P1 drinks from B1, B2
P2 drinks from B2, B3
P3 drinks from B3, B4

with that I can know exactly wich bottle contains poison.
Note that P2 can not die alone.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[fred]: with that I can know exactly wich bottle contains poison.

But how? Let's say all 3 prisoners die. That could mean the poison is in [B1,B3], or [B2,B3], or [B2,B4], or [B1,B2,B3], or [B1,B2,B4], or [B1,B3,B4], or [B2,B3,B4], or [B1,B2,B3,B4]. (I think that's all the possibilities.) How do you know which it is?


"I'm not back." - Bill Harding, Twister
Aj Mathia
Ranch Hand

Joined: Apr 11, 2003
Posts: 478
Originally posted by fred Joly:
I guess it is more complicated than that.
For exemple with 4 bottles , I need only 3 prisonners.
Now i'm trying to extract a method from that.

Let's say 4 bottles B1, B2, B3, B4 and 3 prisonners P1, P2, P3

P1 drinks from B1, B2
P2 drinks from B2, B3
P3 drinks from B3, B4

with that I can know exactly wich bottle contains poison.
Note that P2 can not die alone.


No you still need 4 prisoners in this case
consider P1 P2 and P3 dies
you cannot determine if it was B1 or B4 is poisoned as B2 and B3 are enough to kill em all.
fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
Ah yes Jim an Ajay you're both right!
So, without you, I could have thrown away 2
bottles of decently good wine.

Seriously, there is no better solution than as many prisonners
as bottles ?
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
Originally posted by fred Joly:
Ah yes Jim an Ajay you're both right!
So, without you, I could have thrown away 2
bottles of decently good wine.

Seriously, there is no better solution than as many prisonners
as bottles ?


If there are 4 independent bits of information (whether a given bottle is poisoned) then you need to do 4 independent binary experiments.
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
A variation on Maureen's solution.

1. Line up the 10 prisoners.
2. Give a drop/glass of wine to everyone from a seprate bottle. Name those set of bottles as SET 1 and each bottle with the prisoner's name.
3. After 10 mins give another drop/glass of wine to everyone from a seprate bottle. Name those set of bottles SET 2 and each bottle with the prisoner's name.

4. - 11. Same as above with the bottle set different.

12. Now whenever a prisoner dies you can identify the set as well the bottle according to when the prsioner died.
Tak Ming Laio
Ranch Hand

Joined: Jun 10, 2003
Posts: 37
Originally posted by Anupam Sinha:
A variation on Maureen's solution.

1. Line up the 10 prisoners.
2. Give a drop/glass of wine to everyone from a seprate bottle. Name those set of bottles as SET 1 and each bottle with the prisoner's name.
3. After 10 mins give another drop/glass of wine to everyone from a seprate bottle. Name those set of bottles SET 2 and each bottle with the prisoner's name.

4. - 11. Same as above with the bottle set different.

12. Now whenever a prisoner dies you can identify the set as well the bottle according to when the prsioner died.


I can't see there is any significant modification from Maureen's solution.
The only change is 10 seconds now becomes 10 minutes
Anupam Sinha
Ranch Hand

Joined: Apr 13, 2003
Posts: 1088
Yeah I got it now. My interpretation of her solutionm was wrong. :roll: Yeah she said the exact same thing with time difference being 10 secs.
fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
Originally posted by Ryan McGuire:


If there are 4 independent bits of information (whether a given bottle is poisoned) then you need to do 4 independent binary experiments.


Well simple question, simple answer...
I guess got a little confused with all this wine :roll:
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
(Revisiting this after a few years.)

fred Joly wrote:Thank you both for your replies.
Yes the "bit pattern" is really clever and yet so "simple".
Now I was wondering what can we do if we know that some bottle(maybe none) are poisened and not just one.
The bit pattern does not work anymore.
How many prisonners do we need?

PS : as i understand most of you are asleep by now.
Here (France) it's about 9 AM. So when you wake up, maybe I will
have come up with a solution....I let you know


General answer:
- The king has a total of B bottles of wine.
- A minimum of P1 and a maximum of P2 of them are poisoned.

How many prisoners are needed to find exactly which ones are poisoned?

We just need to extend our basic solution from just one out of 100 possibly poisoned bottles of wine to the total number of possible combinations.

If we know that exactly P bottles are poisoned, then the number of possible combinations of poisoned bottles is C(B, P). *

If P can have any value from P1 to P2, then the total number of combinations is SUM from P=P1 to P2( C(B, P) ) **

The number of prisoners needed to find which one of X possible combinations of bottles is poisoned is CEILING(LOG2 (X)). ***

So the answer is...

CEILING ( LOG2 ( SUM from P=P1 to P2 ( C (B, P) ) ) ) Final answer

Does that "degenerate" correctly?

For B=100, P1=P2=1, we'd expect the answer to be 7.
C(100, 1) = 100
SUM = 100
LOG2(100) = 6.someodd
CEILING(6.someodd) = 7.

For B=100, P1=0, P2=100, we'd expect the answer to be 100.
SUM from P=0 to B ( C(B, P) ) = 2 ^ B
SUM = 2 ^ 100
LOG2 (2^100) = 100
CEILING (100) = 100

Wonderful.

What if the 100 bottles of wine came in 10 cases of 10 and we know that all the bottles from one case were poisoned but then all the bottles were "reshuffled" among the 10 cases.

B = 100, P1=P2=10
(math math math)
answer = 44
Anyone care to either confirm or deny that result?


* C(B, P) = B! / (P! * (B-P)!)
** SUM is usual "sigma" summation operator.
*** LOG2 is the base 2 logarithm operator. CEILING is the "round up" operator. CEILING(2) = 2. CEILING(2.1) = 3.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Puzzle