This week's book giveaways are in the Refactoring and Agile forums.We're giving away four copies each of Re-engineering Legacy Software and Docker in Action and have the authors on-line!See this thread and this one for details.
Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Agile forum!

# Puzzle

Aj Mathia
Ranch Hand
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

fred Joly
Ranch Hand
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
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?

Aj Mathia
Ranch Hand
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
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
Posts: 1055
4
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
Posts: 1090
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
Posts: 38
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
Posts: 1090
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
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.

I guess got a little confused with all this wine :roll:

Ryan McGuire
Ranch Hand
Posts: 1055
4
(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

- 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)). ***

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)