Solving the Mystery of the Poisoned Wine Bottle: O(log n) Solution

[suki2]

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.

 

[davee123]

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

etc.

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.

DaveE

 

[mdelisio]

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).

 

[denverdoc]

Evil king just swears off the sauce?

Restate the question as it is incomplete, not sure what O is?
J

 

[davee123]

Evil king just swears off the sauce?

Restate the question as it is incomplete, not sure what O is?
J

"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?

DaveE

 

[Craigh00000]

"An" answer

The answer can be ONE

 

[Wizardsblade]

didn't it say an evil king? let him die ;)

good job daveE i think that will be the best method

 

[Samadhi]

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:

You could easily devise an algorithm that took O(n) testers-- just have one tester for each bottle, and see who dies.

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).

 

[K.J.Healey]

Evil king just swears off the sauce?

Restate the question as it is incomplete, not sure what O is?
J

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.

 

[Jimmy Snyder]

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.

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.