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. Feb 13, 2007 #1
    An evil king has n bottles of wine, and a spy has just poisoned one of
    them. Unfortunately, they do not know which one it is. The poison is very deadly; just one drop diluted even a billion to one will still kill. Even so, it takes a full month for the poison to take effect. Design a scheme for determining exactly which one of the wine bottles was
    poisoned in just one month's time while expending O(log n) taste testers.
  2. jcsd
  3. Feb 13, 2007 #2
    You need log base 2 of n testers (round up).

    Nobody tests bottle 1
    Tester A tests all bottles that are a multiple of 2.
    Tester B tests all bottles that are a multiple of 4, as well as the 1 bottle before that bottle
    Tester C tests all bottles that are multiples of 8, as well as all 3 bottles before that bottle
    Tester D tests all bottles that are multiples of 16, as well as all 7 bottles before that bottle


    So you get something that looks like:

    1 - nobody
    2 - A
    3 - B
    4 - AB
    5 - C
    6 - AC
    7 - BC
    8 - ABC
    9 - D
    10 - AD
    11 - BD
    12 - ABD
    13 - CD
    14 - ACD
    15 - BCD
    16 - ABCD
    17 - E
    18 - AE
    19 - BE
    20 - ABE

    Each bottle will have a unique combination of testers that die after a month is up. If (for example) bottle 13 is poisoned, testers C and D will die. If bottle 16 is poisoned, A, B, C, and D die. If bottle 1 is poisoned, nobody dies.

    Last edited: Feb 13, 2007
  4. Feb 13, 2007 #3
    You can keep dividing the set in half, maybe making a rule that in the case of an odd numbered set the extra bottle goes in the first half. Each taster is then assigned to taste all the bottles in the first half of each subgroup.

    That is, taster 1 tastes the first N/2 bottles. Taster 2 tastes the first N/4 bottles in each of the 2 groups of N/2 bottles. Keep going until someone is tasting every other bottle. In the end you'll get a tree, with each bottle. This demands that you use at most int(log2(N)) + 1 tasters.

    Very similar in spirit to how many bits does it take to represent a number from 1 to N. Here, the "bi"t of information is poison or no poison (die or live).
  5. Feb 14, 2007 #4
    Evil king just swears off the sauce?

    Restate the question as it is incomplete, not sure what O is?
  6. Feb 14, 2007 #5
    "O" is notation for "worst case" in algorithmic analysis, and is called "Big Oh" notation. It's a way of telling *very* roughly what the worst case efficiency of the algorithm is. So you take the highest power term, strip it of any constants, and that's the notation.

    So let's say I develop an algorithm for, I dunno, figuring out the shortest path between two nodes on a map of N nodes. If my algorithm always takes 3*N^2+1.5N+1 iterations, the "O" notation would be O(N^2). If my algorithm takes between 1 and N+1 iterations, "O" notation would be O(N). If it took 2N+5, it'd be O(N) again.

    So O(log n) testers means that it takes at most some function of log n testers. You could easily devise an algorithm that took O(n) testers-- just have one tester for each bottle, and see who dies. But is there a better solution with worst case O(log n) testers?

  7. Mar 25, 2007 #6
    "An" answer

    The answer can be ONE:biggrin:
  8. Apr 10, 2007 #7
    didn't it say an evil king? let him die ;)

    good job daveE i think that will be the best method
  9. Jun 13, 2007 #8
    Just had this on a test

    I gave the first combination answer (which is what I'm sure the teacher wanted).

    I also gave an alternate solution. This one:
    The teacher specifically clarified that "expending" tasters means that they'd die. So in that case, the above solution is O(1) which is of course better than O(lgn).
  10. Jun 14, 2007 #9
    When I see the O, I think of "On the Order of" so a function 4x^4+x^2+1 is On the order of N^4, or O(N^4). Basically like a comparison of magnitude/order of magnitude for a function.
  11. Jun 15, 2007 #10
    If you correct this to:

    so a function 4x^4+x^2+1 is On the order of x^4, or O(x^4).

    I'll delete this message.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook