Finding lost bottle (algorithm problem)

Question

The question is as follows:

A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on a shelf with $n-1$ bottles of non-reactive material, and the scientist doesn't know which is compound A. There is exactly one bottle of compound A among the $n$ bottles on the shelf. The scientist has $O(log(n))$ beakers full of compound B. How can he determine which of the $n$ bottles is the compound A in exactly 10 days time?

I am a little stuck because I don't know how to narrow down the specific bottle in only 10 days. It is pretty obvious that you can just apply the first half of the bottles to the first beaker, and then if it doesn't react you know that the desired bottle is in the second half and so forth. But how do I narrow it down without witnessing the results of the first few tests?

We need to create something where a series of explosions will help us narrow down which one it is (lets say at first its amongst n/4, then n/10, then n/100, etc). How the heck do I do this?

Answer 1

This is a classical problem that I have previously seen framed as a puzzle rather than a CS question (with some fixed $n$ and fixed number of beakers), though I don't remember any source for it.

You can solve it as follows: Number your bottles from $0$ to $n-1$, and label your beakers from $1$ to $\lfloor\log_2(n-1)\rfloor+1$ (the number of bits needed to represent numbers $0$ to $n-1$ in binary).

Now for every bottle, do the following: let $x$ be the label of the bottle. For every $i$ such that there is an $1$ at the $i$'th position in the binary representation of $x$, put a bit of that bottle's compound in beaker $i$.

Now after 10 days, the beakers which explode will exactly spell out the number of the explosive bottle in binary.