He has 100 wine bottles. One wine bottle contains a deadly poison

The poison given to any person in any quantity will kill that guy in

exactly 10 hrs

The king has 10 prisoners he can experiment upon

The king must figure out which bottle has poison in 10 hrs, after that,

the party will begin!

Take first group of wine bottles and take same amount of wine from all 10 bottles of the group and let first prisoner to have it.

Repeat it for all 10 groups.

After 10 hrs identify the group of wine bottles that has bottle of poison from the dead prisoner.

Leave that group of wine bottle aside and start part with remaining 90 bottles.

[ September 08, 2006: Message edited by: Chetan Parekh ]

My blood is tested +ve for Java.

Mani
*Quaerendo Invenietis*

Originally posted by Chetan Parekh:

Ok, here's a hint: with 10 prisoners the king could test 1024 bottles of wine.

Let's add this to the original problem: The highest priority for the king is finding the poisoned bottle of wine, but he would also like to save as many prisoners as possible. How can the king find out which of the 100 is poisoned AND lose the fewest prisoners on average? What is the expected death rate for the prisoners?

[ September 08, 2006: Message edited by: Ryan McGuire ]

Originally posted by Angela Poynton:

Toom uch hassle for me, I'd just chuck em all in the bin

Hey Angela,

Welcome to ranch ....

This forum is of international readership, please use english while posting your opinion !!!

Otherwise

**Sheriff's**of this forum will delete your account....

Hope for Good Next time

The Best way to predict your future is to create it - Every great individual common man

There is a better way with which you can find out the odd bottle (unlike 10 bottles as it happens in your case). Also, you can test it with just 7 prisoners.

Ok, easy with 7 prisonners but I need 70 hours.(instead of 10 alloweded)

Have you got a solution for 7 prisonners in 10 hours ?

I go on searching.

Originally posted by Ankur Sharma:

Hey Angela,

Welcome to ranch ....

This forum is of international readership, please use english while posting your opinion !!!

OtherwiseSheriff'sof this forum will delete your account....

Hope for Good Next time

Tiny little typo and bit of a colloquialism and I get all that hassle. seesh!

OK In English

It's all too much effort for me. I would just throw all the bottles in the bin

Pounding at a thick stone wall won't move it, sometimes, you need to step back to see the way around.

Originally posted by fred Joly:

Ok, easy with 7 prisonners but I need 70 hours.(instead of 10 alloweded)

Have you got a solution for 7 prisonners in 10 hours ?

I go on searching.

Do you need the results from one taste test to determine what to do next? ...or could you run all your experiments in parallel?

Divide 100 bottles in 2 groups of 50 bottles.

Gave them in two prisonners. One dies, one survives.

result : one dead!

Divide 50 bottles (from the group wich contains poison) in 2 groups of 25 bottles.

Gave them in two prisonners. One dies, one survives.

result : two deads.

...with the same method until 1 bottle with poison found

Originally posted by fred Joly:

Yes, with my method I need the results from one taste test to determine what to do next.

Divide 100 bottles in 2 groups of 50 bottles.

Gave them in two prisonners. One dies, one survives.

result : one dead!

Divide 50 bottles (from the group wich contains poison) in 2 groups of 25 bottles.

Gave them in two prisonners. One dies, one survives.

result : two deads.

...with the same method until 1 bottle with poison found

Do you need to use two prisonoers for experiment 1? Couldn't you just have a single prisoner test bottles 1-50? If he dies, one of those bottle is poisoned. If he lives, the poison must be in bottle 51-100, right? So you really need one prisoner per experiment.

So depending on the outcome of experiment 1 (using bottles 1-50 and 51-100), you would try either experiment 2a (bottles 1-25 and 26-50) or experiment 2b (bottles 51-75 and 76-100). Could you perform both 2a and 2b at the same time on the same (single) prisoner simultaneously with each other AND with experiment 1? It's just that the results of either experiment 2a or 2b will be meaningless depending on the outcome of experiment 1. For instance, if prisoner 1 dies then the poison must be somewhere in bottles 1-50. In that case experiment 2b provided no information, but experiment 2a did.

Now extend that concept to experiments 3a,b,c and d, 4a,b,c,d,e,f,g and h, etc.

Cool?

Yes, with my method I need the results from one taste test to determine what to do next.

Divide 100 bottles in 2 groups of 50 bottles.

Gave them in two prisonners. One dies, one survives.

result : one dead!

Divide 50 bottles (from the group wich contains poison) in 2 groups of 25 bottles.

Gave them in two prisonners. One dies, one survives.

result : two deads.

...with the same method until 1 bottle with poison found

This way won't it take more than 10 hours?

sorry for the mistake.I gave the image path thinking that this image will be uploaded to javaranch and will be displayed,but unfortunately it showed the link to my desktop.

Anyways here is the link to the page that contains the image i am talking about

Arrange bottles in the formation of 10x10 as shown in the figure.

Place the name of prisoners along the x and y axis of the square(prisoners are named with A-J).

Now for'A' there are bottles with label 1,11,21,31,...91 aligned across and 1,2,3,4..10 downwards.

So take 1 drop each from 1,2,3,4...10 and 1,11,21,31....91,make a mixture of them and give to 'A'. Do the similar process for others as well.

So this way, each bottle's content will be consumed by exactly 2 prisoners.

So at the end of 10 hours exactly 2 prisoners will die. matching their names with the square, we can find out the poisionous bottle.

[ September 08, 2006: Message edited by: Nitin Nigam ]

[ September 08, 2006: Message edited by: Nitin Nigam ]

[ September 08, 2006: Message edited by: Nitin Nigam ]

[ September 08, 2006: Message edited by: Nitin Nigam ]

[Andrew: inlined image]

[ September 09, 2006: Message edited by: Andrew Monkhouse ]

Nothing is impossible; for those who doesnt have to do it themselves.

myjotting.blogspot.com

So is the king willing to risk throwing out one perfectly good bottle of wine, along with the poison one in order to save the lives of five prisoners? Doesn't sound like any king I've ever heard of. I'm still waiting for the "seven prisoners die" solution.

Sheriff

**[Ryan]: Let's add this to the original problem: The highest priority for the king is finding the poisoned bottle of wine, but he would also like to save as many prisoners as possible. How can the king find out which of the 100 is poisoned AND lose the fewest prisoners on average? What is the expected death rate for the prisoners?**

I don't know that this is optimal, but I get an expected loss of 3.16 prisoners, with a range of 0-7.

[ September 08, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Originally posted by Jim Yingst:

I don't know that this is optimal, but I get an expected loss of 3.16 prisoners, with a range of 0-7.

Hmmm... I came up with an expected loss of only 2.32 prisoners and a max of only 3. If bottle 1 is poison, nobody dies; bottles 2-11, one prisoner; bottles 12-56, two prisoners; 57-100, three prisoners. (1*0 + 10*1 + 45*2 + 44*3)/100 = 2.32

[ September 08, 2006: Message edited by: Ryan McGuire ]

Sheriff

Originally posted by Greg Charles:

OK, maybe I understand now, but it seems by Nitin's method we'd have to throw out two bottles. Say prisoners B and C died, then we'd have to throw out bottles 13 and 22. (That's with B drinking 11 - 20, and 2, 12, 22, 32, 42, ... and C drinking 21 - 30, and 13, 23, 33, 43, ...) Am I missing a detail there? In certain cases, ie., the ones on the diagonal, only one prisoner would die and the offending bottle would be exactly identified. The way I've drawn it out, those would be bottles 1, 12, 23, 34, etc.

Hi greg you got my point. In this case king has to throw 2 bottles. I think we can further refine the solution so that we have to throw only 1 bottle. I am trying to do that, will come up with the solution soon.

Nothing is impossible; for those who doesnt have to do it themselves.

myjotting.blogspot.com

Take the 7 prisioners and and do some binary arithmetic

0000000 --> 1st wine bottle.All zeroes mean nobody drinks the first bottle

0000001 --> 2nd wine bottle.Only the prisioner at Pos. 1 drinks from bottle 2

0000010 --> 3rd wine bottle.Only the prisioner at Pos. 2 drinks from bottle 3

0000011 --> 4th wine bottle. Only the prisoner at Pos. 2 n 3 drink from bott 4

and so on ......

1100100 --> 100th bottle.Only prison. at pos. 7,6 and 3 drink from bott.100

Each bottle can be uniquely represented by prisoner positions in binary format .

At the maximum 6 prisoners will get killed if they consume the bottle number 64 ( 0111111 ) .....

Case is closed ....

I hope the king invites me over for the party , abd treats me with some of his best wines

[ September 09, 2006: Message edited by: Vivek Pandey ]

Vikrant Pandit

Sheriff

**[Greg]: I believe it is the solution that Jim was alluding to.**

Yep. And Mani. And I expect Ryan knew too, but skipped on to the next problem.

**[Greg]: However, Ryan alludes to an improved solution that lowers the expected mortality rate for prisoners**

Hint: [In Vivek's list of numbers, the more 1's a number has in it, the more fatalities there will be if that bottle has the poison. How can this be minimized?]

[ September 11, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Originally posted by Ryan McGuire:

Hmmm... I came up with an expected loss of only 2.32 prisoners and a max of only 3. If bottle 1 is poison, nobody dies; bottles 2-11, one prisoner; bottles 12-56, two prisoners; 57-100, three prisoners. (1*0 + 10*1 + 45*2 + 44*3)/100 = 2.32

[ September 08, 2006: Message edited by: Ryan McGuire ]

If the selection of prisoners is not done properly a few(couple) of prisoners will face a higher chance of dieing. thats the guys who drink from bottle 57-100.

another solution without the exact 10 hr restriction would be to get the prisoners to drink from bottles 2-56 and then 57-100 say 10 seconds after the first drink.

if the king is lucky 99 bottles will be ready to be served in 10 hrs

if not in 10 hrs 10s.

*You think you know me .... You will never know me ... You know only what I let you know ... You are just a puppet ...* --CMG

With or without introducing these 10 seconds, the dieing probabilities distribution among the 10 prisoners are the same, which is:

8 of the prisoners have dieing probabilites of 0.09833...

2 of the prisoners have dieing probabilites of 0.10166...

(assume the most even distribution)

Maybe after introducing the 10 seconds, you can claim that the 10 prisoners have the same probabilites die exactly in 10 hours, but the probabilites die in 10 hours 10 seconds or before is still difference.

Originally posted by Ajay Mathew:

If the selection of prisoners is not done properly a few(couple) of prisoners will face a higher chance of dieing. thats the guys who drink from bottle 57-100.

Indeed. The solution depend on the king's priorities:

If it's more important to save as many prisoners on average as possible, then the mortality rate can be kept to 2.32 but with uneven chances across the prisoners. Eight prisoners have a .16 chance of dieing and two prisoners have a .17 chance of not seeing another day. (Tak Ming Laio, how did you get .09833 and .10166?)

If the king is more intrerested in being perfectly fair, then he could use five-bit patterns instead of three-bit patterns for bottles 57-100. This would raise the exptected mortality rate to 3.20. But then every prisoner would then have the exact same .25 chance of getting the poison.

**Next variation:**Mapping the 100 bottles onto...

- 1 zero-prisoner pattern

- 10 one-prisoner patterns

- 45 two-prisoner patterns

- 44 five-prisoner patterns

...provides a 3.20 mortality rate and a perfectly fair .25 chance of dieing for each prisoner. Is there a way to assign prisoners to bottles that is still perfectly fair but provides a chance of dieing lower than .25 for each of them?

[ September 12, 2006: Message edited by: Ryan McGuire ]

Get a stopwatch. Line up prisoners. Give each one drop from bottles 1 - 10. Repeat 10 seconds later with bottles 11 - 20 and so on every 10 seconds until all bottles are tested.

After 10 hours, see if anyone dies. If yes, release all bottles to the party except the one that killed the prisoner. If no, release the first 10 bottles to the party, wait 10 seconds and repeat. Keep repeating until the poison is found, then release the remaining bottles to the party.

Can anyone tell that I'm working on recursion in my textbook right now?

[ September 12, 2006: Message edited by: Maureen Augustus ]

"Sex and drugs and women being set on fire! I've never heard of such a Christmas!" - Christine Baranski in "The Ref"

Originally posted by Ryan McGuire:

If it's more important to save as many prisoners on average as possible, then the mortality rate can be kept to 2.32 but with uneven chances across the prisoners. Eight prisoners have a .16 chance of dieing and two prisoners have a .17 chance of not seeing another day. (Tak Ming Laio, how did you get .09833 and .10166?)

Yes, I calculated wrongly. When I think it over the probalilities distribution should be:

8 prisoners have chance of dieing 0.23

2 prisoners have chance of dieing 0.24

The expected number of prisoners die is 2.32, so the chance of dieing for each prisoner should be 2.32/10 = 0.23 (if chance is even distributed), right?

For the 8 more luck prisoners, they take drops from:

1 out of the first 10 bottles

9 out of the second 45 bottles

13 out of the last 44 bottles,

so they only get drosp from 1+9+13=23 bottles out of the 100 bottles,

therefore, their chance of dieing is 23/100.

Originally posted by Tak Ming Laio:

Yes, I calculated wrongly. When I think it over the probalilities distribution should be:

8 prisoners have chance of dieing 0.23

2 prisoners have chance of dieing 0.24

Yup, you're right. I made a math error to come up with those .16/.17 and .25 numbers earlier. I should have said .23 and .24 are the best uneven chances. Using 44 five-bit patterns for bottles 57-100 allows us to distribute the 10 prisoners evenly but raises the mortality rate to 3.20 and gives each prisoner a .32 chance of getting poison.

Try this scheme:

Use 48 of the 120 possible three-bit patterns for bottles 53-100, you should end up using four of the prisoners (call them the Read Team) 15 times and six of them (call them the Blue team) 14 times. Use the 45 two-bit patterns for bottles 8-52. Those are all fair. Use the six prisoners from the Blue Team to sample bottles 2-7. Each prisoner is used in 24 bottles giving EVERY prisoner .24 chance of getting the poison. This is only slightly worse than some prisoners having a .23 chance and some a .24 chance. (Of course the average mortality rates is raised from 2.32 to 2.40.)

Nothing is impossible; for those who doesnt have to do it themselves.

myjotting.blogspot.com

Sheriff

*got*solutions to this - the only point I see in continuing discussion now is to explore variations which have different benefits. I think Maureen's solution is an excellent alternative. Note that at least 10 bottles become available to for the party immediately after the 10-hour mark. That ought to be enought to get the party started, at least.

Personally I'd probably use 10-minute delays between the groups, rather than 10 seconds. People don't need to drink

*that*quickly, and I'd rather have some extra certainty about exactly which bottle is poisoned.

"I'm not back." - Bill Harding, *Twister*

Originally posted by fred Joly:

Just by curiosity : does this puzzle have any practical application ?

Does the

**puzzle**have any application? Sure, it helps us exercise our ability to solve problems. Encoding bottle numbers using "bit patterns" of prisoners is a fairly clever idea. The subsequent refinement of that solution to save as many prisoners as possible also shows us that the first/simplest solution is always the best.

Does the

**answer**to this puzzle have any application? I suppose we could come up with some contrived example:

Let's say you have a network of 1000 servers with a ring topology and you know that exactly one of them is misprocessing messages in some way. Let's say you can construct request messages that can be serviced by any arbitrary combination of servers. Each server looks at each message that goes by and either passes it on perfectly or processes it somehow and then passes it on.

By applying the lesson we learned with the wine/prisoner puzzle, we know that we can figure out which server is "poisoned" by sending out only 10 "prisoner" messages and seeing which ones come back "dead". Also, you don't have to wait for each message to make the full round trip (either live or die) before sending out the next.

Even if the king cares nothing for the prisoners, he definitely doesn't want to waste wine.

Henry

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

It is sorta covered in the JavaRanch Style Guide. |