The general problem can be stated as follows:
There are 30 identical bottles of wine, one of which is poisoned. A rat will die in 3h after tasting the poison. How many rats do you need to test for the poisoned bottle for the shortest time frame possible?
What do you think? The best answer I could find on Quora is to apply binary assignment. Each bottle should be labeled with a number represented in binary format. For example, the first bottle is 0001, the second, 0010, the third, 0011…
Each rat should hold a position of significance in these binaries. The rats must taste all bottles with a label containing non- zero at the position of significance it holds. See picture below:
Now that a rat may taste multiple bottles, how do we decode the bodies of dead rats, how do we determine the cause of their death? For example, let’s assume bottle 3 is the one. Rat 1 and 2 would die. If bottle 1, rat 1. If bottle 4, rat 3.. So on…
While this is the most efficient approach in terms of the number of rats required, it’s the most brutal and cruel for the rats. Imagine the worst case scenario, the poisoned bottle is 7 (111), all the rats would die for the cause.
I did not think of this solution myself. What I could propose is to recruit N-1 rats. I feel that one rat dies is enough. Maybe I am too humane this time.
I encountered this problem during a recent interview. Personally I think this is a great question to classify the shortlisted candidates. I did not answer this question because I could not give the perfect solution. Someone with negotiation skill would ask for acceptable solutions. Someone willing to take risks would opt for the solution above. Someone with a heart for animals like me would choose the N-1 solution.