aspose file tools*
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
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Puzzle" Watch "Puzzle" New topic
Author

Puzzle

Sameer Jamal
Ranch Hand

Joined: Feb 16, 2001
Posts: 1870
A king is going to throw a party 10 hours from now

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!
Chetan Parekh
Ranch Hand

Joined: Sep 16, 2004
Posts: 3636
Divide 100 bottles in the 10 groups of 10 bottles.

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 Ram
Ranch Hand

Joined: Mar 11, 2002
Posts: 1140
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.


Mani
Quaerendo Invenietis
Chetan Parekh
Ranch Hand

Joined: Sep 16, 2004
Posts: 3636
Originally posted by Mani Ram:
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.


Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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 ]
Angela Poynton
Ranch Hand

Joined: Mar 02, 2000
Posts: 3143
Toom uch hassle for me, I'd just chuck em all in the bin


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

Joined: Dec 27, 2005
Posts: 1249

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
Chetan Parekh
Ranch Hand

Joined: Sep 16, 2004
Posts: 3636
Originally posted by Ankur Sharma:


Hey Angela,
......
Hope for Good Next time



fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
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.
Angela Poynton
Ranch Hand

Joined: Mar 02, 2000
Posts: 3143
Originally posted by Ankur Sharma:


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



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
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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?
fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
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
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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?
Ritika Saxena
Ranch Hand

Joined: Jul 02, 2006
Posts: 51
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?
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
Originally posted by Ritika Saxena:

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


Right. That's exactly what fred said in his previous post.
Nitin Nigam
Ranch Hand

Joined: Jul 03, 2006
Posts: 129
Hi ranchers,
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
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2861
    
  11

I'm not quite fathoming Nitin's method, and the image is currently a link to his C: drive. Still, it's not impossible to be brilliant and idiotic at the same time. I've proved that many times!
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
Originally posted by Nitin Nigam:


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


If prisoners A nd B die, is the Ath bottle in the Bth row or the Bth bottle in the Ath row?
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2861
    
  11

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.

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.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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 ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Ah, I see. I was still thinking in terms of using only 7 of the prisoners. But by using more, you can decrease the overall mortality. Clever.
Nitin Nigam
Ranch Hand

Joined: Jul 03, 2006
Posts: 129
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.
Vikrant Pandit
Ranch Hand

Joined: Mar 27, 2006
Posts: 245
I think I have the "7 - prisoner" reply

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
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2861
    
  11

Yes, Vivek, that's an excellent solution. I believe it is the solution that Jim was alluding to. However, Ryan alludes to an improved solution that lowers the expected mortality rate for prisoners (and still doesn't waste a bottle of wine.) I'm still trying to figure out how that would work.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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 ]
Aj Mathia
Ranch Hand

Joined: Apr 11, 2003
Posts: 478
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
Tak Ming Laio
Ranch Hand

Joined: Jun 10, 2003
Posts: 37
I can't see why introduce these 10 seconds will make the dieing probabilities of the 10 prisoners become equal.

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

Joined: Jan 19, 2006
Posts: 55
Congratulations for these solutions!
quite more sophisticated than my first idea

for Ryan : yes Cool, thank you
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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 ]
Maureen Augustus
Ranch Hand

Joined: Aug 18, 2006
Posts: 72
Do you think the king is willing to release bottles in increments? Because I have a solution that would kill only one prisoner, but take 10 hours, 1 minute and 30 seconds. It's based on the fact that the poisoned wine kills in EXACTLY 10 hours.

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"
Tak Ming Laio
Ranch Hand

Joined: Jun 10, 2003
Posts: 37
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.
Tak Ming Laio
Ranch Hand

Joined: Jun 10, 2003
Posts: 37
Maureen Augustus's suggestion make me think Ajay Mathew's solution again, and I found that Ajay Mathew is right. We can test 55 bottles first basically using Ryan McGuire's solution. After 10 seconds we can test the remaining 45 bottles using the 2-prisoner-die pattern. Then the expected number of prisoners die is only 1.9 and the chance is evenly distributed among the prisoners, each have chance of 0.19 to die.
fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
Just by curiosity : does this puzzle have any practical application ?
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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.)
Nitin Nigam
Ranch Hand

Joined: Jul 03, 2006
Posts: 129
Guys!!! Basic requirement in this puzzle is to do something that gives result in one go. No 10-15 second trick. This is a well made puzzle, not a real situation where you can get 10-15 second hear or there. So please try to find the solution keeping in mind that you have to make prisoners drink only once.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Nitin, the basic requirement is impossible since any of these solutions require nonzero time to set up, and the requirements don't allow any slack in the solution. The party is supposed to start in 10 hours, and any solution requires at least 10 hours plus setup time to get results. So we need to bend the rules a little bit anyway. And we've already 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.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18996
    
  40

Mapping the bottles by the bit pattern (with number of bits as a priority) is really clever. Not only will it lower the mortality rate, but it also saves wine, as less will be needed for testing.

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

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
fred Joly
Ranch Hand

Joined: Jan 19, 2006
Posts: 55
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Puzzle