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.
     
  22. Jun 17, 2005 #21
    What is your solution for the antidote problem? Just curious, mine works in two months tops.
     
  23. Jun 17, 2005 #22
    You mentioned you 'proved' the minimum maximum amount of time for the antidote problem was 4 months? What's your proof?
     
  24. Jun 17, 2005 #23
    My solution is the same that I have written in reply#10. You'd have to extend a bit further to accommodate the antidote. The time taken would vary as per the case. In the worst case mentioned before, you know which digits are same so, you just need one month more. In the best case, you have the poison and 9 persons. Work with the other digits(using the poison to isolate the antidote). Well, I've realised that this might not work in all cases(people may be less in some cases), but I think It works in most cases. That's why I want to see other solutions.

    Besides, you should realise that the poison + antidote problem wasn't set by me. It was set by NateTG. I just set the first problem(POISON ONLY). So I'm sure only about that particular solution. What I can assure you is that my method will find the poison in 4 months max., but it will not necessarily find the ANTIDOTE, with limited no. of people.
     
  25. Jun 17, 2005 #24
    The proof was a rigorous proof(see #11). I was talking wrt my algorithm only . It applies to my algorithm at least, i.e We can take any number system and get the answer in max. of 4 months. For number systems above 10, it becomes clear that the number of months would be more than 4. Hence I say that the minimum maximum is 4 months. What I mean is that you do not need more than 4 months to find the poison. It can take 2,3 or 4 months depending on the position of the bottles, but not more than 4.

    I'm sorry if I was not clear in explaining my algorithm.
     
    Last edited: Jun 17, 2005
  26. Jun 17, 2005 #25
    The antidote can be found in no more than TWO months.

    Okay, so I was working on a set-theory proof, but it occured to me I can explain things much more easily:

    Consider a set of N people, 2^N bottles, exactly one of which has poison and one (different bottle) has the antidote.

    Organize the bottles in base 2: (x1, x2, ... , xn).

    In the first month, the ith person drinks precisely those 2^N bottles where the ith digit is 0:

    (x1,x2...,0,...,xn).

    Just like 20answer's proof for the poison problem. So far.

    Two cases.

    Case 1: At least one person, say the jth person, dies after a month.
    Then the set of all bottles with jth digit equal to zero contains the poison, AND this same set does not contain the antidote.
    Furthermore (this is subtle): Since the antidote exists, and is not in this set, it must be in the complement of this set, which is precisely the set of bottles with jth digit equal to 1!

    Formally: If {j1,...,jk} are those people who did die, then the binary representation of the poisoned bottle has all jk's equal to 0, and the antidote's representation has those digits equal to 1.

    Consider the set of all people who did not die; i.e., the complement of the set of dead people. (Special case: if this set is empty - if everyone died - then the poison must have been in the bottle corresponding to (0,0...0) all zeroes, and the antidote at (1,1...1) , and we're done! Because if mth digit of poison is 1, mth person did not drink it and lived; likewise, if antidote's mth digit was 0, then the mth person drank the antidote and lived).
    The digits these people represented are precisely those digits of the antidote's location which we do not know (see above). Let each kth person drink all bottles in the intersection of the sets of all the bottles the dead people drank; the poison is obviously in this set, and the antidote obviously isn't. Then, let each kth person drink all bottles with their kth digit equal to 0 (again!). This will uniquely determine the remaining digits of the antidote's location: if kth person dies, kth digit is 1, else it is 0.

    Case 2: No one dies in the first month.
    Then the either the poison must be in (1,1,1...1) or the antidote in (0,0,0...0). If neither of these were true - kth digit of poison were 0, and mth digit of antidote were 1 - then mth person would drink poison, but not antidote because mth person only drinks bottles with 0 in mth digit.
    Then we progress exactly as in month 1, with two changes: every person additionally drinks bottle (1,1,1...1). If no one dies, that means (0,0,0...0), the only other bottle drank in common by everyone, was in fact the antidote; otherwise, (1,1,1...1) was in fact poison (see above), and thus the digits of the antidote are uniquely determined, by those who do not die.

    Squid erat demonstratum.

    This result allows us to find the antidote in a set of 2^k bottles, with only k people, in no more than 2 months.

    An example:
    5 people, 2^5=32 bottles. 5-digit binary representations: (x1,x2,x3,x4,x5). Poison is in (1,1,0,1,0), antidote in (1,0,0,1,1).

    month 1: Person #1 drinks 16 bottles, namely all (0,x2,x3,x4,x5).
    Person #1 does not drink from the poisoned bottle, nor the antidote.
    Persons 3 and 5 drink poison; person 5 drinks antidote, person 3 doesn't. The only person to die is person 5.

    Month 2: Everyone drinks all bottles of the form (x1,x2,x3,x4,0), including (1,1,0,1,0) the poison, but not including (1,0,0,1,1) the antidote.
    Person 1 then drinks all (0,x2,x3,x4,x5), which does not include the antidote. Persons 2 and 3 drink the antidote; 1 and 4 die. Thus the antidote must have 0's in digits 2 and 3; and 1's in digits 1,4, and 5.
    (1,0,0,1,1).

    Only two months!

    edit: emphasis
     
    Last edited by a moderator: Jun 17, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook