$\textbf{Bitter Water}$
There are $1000$ bottles of water. All of them are tasteless except one which tastes bitter. How do you find the bottle of bitter water in the smallest number of sips?
$\textbf{Solution}$
A total of $10$ sips are required.
- Equally divide the $1000$ bottles into two groups. Then, take a small sample from each of $500$ bottles in one group and mix them up. If the mixed water tastes bitter, proceed to the next step with these $500$ bottles. Otherwise, proceed using the other group.
- Equally divide the $500$ bottles into two groups. Then,take a small sample from each of the $250$ bottles in one group and mix them up. Proceed to the next step with these $250$ bottles if the mixed water tastes bitter, or the other group if the mixed water is tasteless.
- Adopt the same strategy with $125$ bottles.
- Now because the number of bottles is odd, we split it to $61$ vs $64$. The worst case is to check the $64$ bottles. Because $64$ is a whole power of $2$, all the remaining splits will be even.
Repeating this process till we can uniquely identify the bottle containing bitter water. It will require no more than $10$ sips.
$\textbf{Note}$
The background of this strategy is the binary search algorithm in computer science. This algorithm can be used to identify one object from a collection of $n$ unsorted objects. The algorithm always divides the collection into two sub-collections of equal or similar sizes and then determines which sub-collection containing this target object. In this example, the total number is $1000$. Because $2^9 < 1000 < 2^{10}$, therefore a total of $10$ searches are required.