Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Poison bottles

  1. Jun 16, 2005 #1
    I've mentioned this before, but that thread was moved to homework, so I'll put it here again:
    There are 1023 bottles. One out of them is a poison bottle. You have ten persons who can be sacrificed for the purpose. Find the poison bottle in a systematical way.

    Hint:Use the unique property of the number 1024.
     
  2. jcsd
  3. Jun 16, 2005 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Um..
    This is *really* easy. You draw lots. The person who looses takes a sip from each of the bottles except for one, one by one, to see whether it's poison. Give the other nine shovels to dig a grave.
     
  4. Jun 16, 2005 #3
    LOL!!
    Since the original question was so **easily** solved! Let me make it a bit harder.

    "The person dies of the poison can be seen after a month only. So we dont have immediate results. However we would like to know which is the poison bottle immediately after a month. So we dont have much time. Can we devise a suitable strategy now?"

    Ofcourse this one probabily is solved in this forum before :uhh:

    -- AI
     
    Last edited: Jun 16, 2005
  5. Jun 16, 2005 #4

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Why not make it fun, and put a bottle of antidote in as well - so anyone who drinks the poison and the antidote survives.

    Now, assuming a one month activation time, the challenge is to identify the poison and the antidote as quickly as possible, using 10 people.
     
  6. Jun 16, 2005 #5
    You probably need 10 months.
     
  7. Jun 16, 2005 #6

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    I'm fairily sure it can be done in 8 months or less.
     
  8. Jun 16, 2005 #7
    number the bottles 0-1023 in binary numbers (10 digits), each bottle number with first digit a "1" is drunk by person 1, second digit a "1"? then person 2 drinks some, etc. etc. If say, the 1st 4th and 9th die then then bottle was 1001000010 (decimal 578)
     
  9. Jun 16, 2005 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Can you do the harder version?
     
  10. Jun 17, 2005 #9
    Excellent solution by 20questions. I wouldn't have got it for a whole life time.
     
  11. Jun 17, 2005 #10
    I got it

    Right, 20questions gave the answer I expected. Well Done!!
    About the harder question: (in white)
    The no. 1023 is 1111 1111 11 in base 2.
    If we proceed as in the first part, we take only the first digit and two people. If the poison and the antidote have the same first digit, no one will die. If they have different digits, the one who gets the poison will die.

    -Case 1: One dies: We have now narrowed down the range. The poison is obviously in the other digit. So, we can proceed as in the first part to find the answer with 9 people and 9 digits. Done. Took two months.

    -Case 2: No one dies: We can't narrow it down now. We just proceed with the next digit and so on. At least one digit will be different. When we find the different digit, one person will have died. We now eliminate half of the numbers. Antidote is eliminated. 9 digits and 9 persons. Proceed as in first part. It can take a varying amount of time. Minimum is 3 months, maximum is 11 months.

    This is what I believe Jimmy was referring to. Well, we can shorten the time further by using the ten persons for 5 digits simultaneously. So, maximum time is four months.

    With this method, we can find the antidote as well. I'll just leave it to you guys as an exercise.
    o:)
     
    Last edited: Jun 17, 2005
  12. Jun 17, 2005 #11
    Other way

    Here's another way. (for the poison only):
    We shouldn't limit ourselves to binary system.
    1023 in base 3 is 1101 220. That means a max. of 4 months, using 3 persons per digit.
    1023 in base 4 is 3333 3. That means a max. of 4 months, using 4 persons per digit.
    1023 in base 5 is 1304 3. That means a max. of 4 months, using 5 persons per digit.
    1023 in base 6 is 4423. That means a max. of 5 months, using 6 persons per digit.
    1023 in base 7 is 2661. That means a max. of 4 months, using 7 persons per digit(except the first which needs 3 persons).
    1023 in base 8 is 1777. That means a max. of 4 months, using 8 persons per digit(except the first one which needs 2 persons).
    1023 in base 9 is 1356. That means a max. of 5 months, using 2 persons for first digit, 9 persons for 2nd, 3rd and 4th digit.
    1023 in base 10 is 1023. That means a max. of 5 months, using 10 persons per digit (except the first).


    I hope everyone gets the point and I really got a lot more out of the puzzle than I expected.(Thanks to NateTG)
     
    Last edited: Jun 17, 2005
  13. Jun 17, 2005 #12
    No, I was just not thinking about the problem correctly. I figured for 1 guy to drink from half the bottles and then wait a month to see if he died. Then continue on in a binary search for 9 more months. This solution takes 10 times as long as the solution given by 20questions. Before 20questions posted the correct solution, I had already come up with a different solution requiring 4 months, but there is no point in proposing it now.
     
  14. Jun 17, 2005 #13
    Well, Jimmy you should write your solution down at least to give us a new way of thinking about the problem. I've already proved sufficiently that the minimum maximum is 4 months. Post it please. :cry:
     
  15. Jun 17, 2005 #14
    20question's solution only requires one month.
     
  16. Jun 17, 2005 #15
    Well, it does but it doesn't account for the antidote. If the antidote is included, the solution points to the wrong bottle. In order to correct it, I introduced the elimination method.

    I also said that the minimum maximum is 4 months. This means, if you are really unlucky and are not able to eliminate any bottles till the last step, you will take 4 months. You can of course be stupid and take more time, but you don't need to. This is the maximum time that my algorithm needs.
    You can of course be really lucky as in case 1(see reply#10) and find the poison in 2 months.
    By the way, if you haven't got it yet, I left finding the antidote as an exercise. In fact, you have to be lucky(or take an more time and people) to find the antidote.
    Hence, the time period has to be between 2 and 4 months.
     
  17. Jun 17, 2005 #16
    I got at the most 3 dead in 4 months. May be someone can find more optimum way of finding out the poison with less casualities in less time.



    1st month :

    10 groups of bottles; 1 person for each group; 102 bottle in each group; (10 * 102 = 1020) ;
    3 bottles reserved.

    2nd month :

    case 1: No one died; then 3 persons for the remaining 3 bottles .
    case 2: 1 died. 102 bottle from his group divided into 9 groups ;
    11 bottle in each group. 9 X 11 = 99;
    3 bottles reserved.



    3rd month :

    case 1.1 : 1 of the 3 died ; the bottle is fixed. in 2 months with 1 dead.

    case 2.1 : No one died; 3 persons for the remaining 3 bottles.
    case 2.2 : 1 died. 11 bottles from his group for 8 persons, one each. 8 X 1 = 8;
    3 bottles reserved.


    4th month :

    case 2.1.1 : 1 of the 3 died; the bottle is fixed.. in 3 months with 2 dead.

    Case 2.2.1 : No one died; 3 persons for the remaining 3 bottles.
    case 2.2.2 : 1 died. the bottle is fixed. in 3 months with 3 dead.


    5th month :

    case 2.2.1.1 : 1 died. the bottle is fixed. in 4 months with 3 dead.
     
  18. Jun 17, 2005 #17
    Good work, everneo.
    But you must realise that the solution obviously was very rigorous and took you a lot of time. If, now, I give you the number 262,143, you will need even more cases and subcases and sub-sub-cases to find an algorithm. So, such a solution would be frowned down upon.
    But, a knowledgable person will tell you that 262,143 is 777 777 in octal system.
    So, the algorithm is set. Take 8 people and give them bottles beginning with one digit each. Again take 2 cases(see reply#10). Do this and you will find the poison bottle with 14 people in 7 months.

    Your effort really is worthy of praise, but it cannot extend to significantly more people.
    As for your question, I don't think anyone will be able to find an optimal solution which is generalisable(By the way, when I was introduced to this problem, I found that I could find the poison bottle with 8 people in 4 months, by your method)
     
  19. Jun 17, 2005 #18
    I don't know what's going on, are you people approaching the POISON ONLY problem or the POISON + ANTIDOTE problem? Everneo and ssj5harsh: I'm assuming your methods are dealing with the POISON ONLY problem?

    edit: everneo, your method as I've read it is in general is THE optimal one, if you're seeking to minimalize casualties. 20answer's is the optimal solution for minimizing time.

    edit2: mea culpa, an improvment on everneo's method is for a single person to go through bottle by bottle... hence solving the question with exactly one fatality.
     
    Last edited by a moderator: Jun 17, 2005
  20. Jun 17, 2005 #19
    I solved it! The antidote version of the problem! It can be done in two months! I'm writing my proof now, it'll be up in some minutes.
     
  21. Jun 17, 2005 #20
    Everneo's solution is for the POISON only. It has lowest and definite casualties. The best solution for the poison problem is 20questions' method.
    For the POISON + ANTIDOTE problem, I (obviously) agree with my solution. But I have yet to see Jimmy's solution. I'd like to see your solution as well.

    The two problems are separate problems.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Poison bottles
  1. Message in a bottle (Replies: 20)

  2. Have I been poisoned? (Replies: 15)

  3. Poison in our pans (Replies: 23)

  4. Klein Bottles (Replies: 2)

Loading...