Question

An evil king has n bottles of wines, 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 an algorithm for determining exactly which one of the wine bottles was poisoned in just one month’s time while expending O(log n) taste testers.

Answer 1

The bottles are labelled from 1 to n in binary. Example is shown below:

Bottle 1 0000

Bottle 2 0001

Bottle 3 0010

Bottle 4 0011

Bottle 5 0100

Bottle 6 0101

Bottle 7 0110

Bottle 8 0111

Bottle 9 1000

Bottle 10 1001

Let,

there be a log2n cups. Label the cups from 1 to log2n.

Pour a drop of the wine from all the bottles whose kth bit in the code is 1 to the cup k.

From each bottle whose first bit is 1, a drop is poured to cup 1.

From each bottle whose second bit is 1, a drop is poured to cup 2.

From each bottle whose third bit is 1, a drop is poured to cup 3.

From each bottle whose log2kth bit is 1, a drop is poured to cup log2k.

Map the taste testers to the respective cups.

i.e., Tester 1 tastes in cup 1, Tester 2 tastes in cup 2, 3 tastes in cup 3........

In one month some of the testers will be dead.

The wine that was present in the cups of all the dead testers is the poisoned wine.