Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

Puzzle

 
Ranch Hand
Posts: 478
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ?
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 40
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
(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.
 
Poop goes in a willow feeder. Wipe with this tiny ad:
Free, earth friendly heat - from the CodeRanch trailboss
https://www.kickstarter.com/projects/paulwheaton/free-heat
reply
    Bookmark Topic Watch Topic
  • New Topic