Aj Mathia

Ranch Hand

Posts: 478

posted 10 years ago

100 prisoners

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

Posts: 55

posted 10 years ago

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.

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

Sheriff

Posts: 18671

posted 10 years ago

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?

**[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

Posts: 478

posted 10 years ago

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.

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.

*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

Posts: 55

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 10 years ago

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

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

posted 10 years ago

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.

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: 40

1

posted 10 years ago

I can't see there is any significant modification from Maureen's solution.

The only change is 10 seconds now becomes 10 minutes

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

fred Joly

Ranch Hand

Posts: 55

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 7 years ago

(Revisiting this after a few years.)

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

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.

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.