The king has hosted a dinner which is about to start in one hour and guests have arrived. The king plans to offer his exquisite wine collection to the guests. There are 16 different bottles of wines (labeled 1 through 15) available and they are to be served to the guests.
The minister comes to know from a trusted source that one of the bottles is poisoned. Also, the poison takes one hour to come into affect and kill someone.
It is a tough time for the king and the minister and it becomes utmost priority to identify the poisoned bottle. The only way to test the bottles is to make someone drink from the bottle and wait for an hour. If the person dies then the bottle is poisoned. The king also identifies that the poison has the same effect on lab rats as it has on humans.
The task at hand is to identify the poisoned bottle. You can use the rats from the king’s laboratory. Borrowing each rat incurs a cost and it is very important to use least number of rats.
Solution – Identify the Poisoned Bottle
The easiest way is to use 15 rats (label them 1 through 15) and make each of them drink from a bottle. If a rat with label X dies then we get to know that the bottle with label X is poisoned.
But as we know that we need to minimize the cost of borrowing rats, which translates to using minimum number of rats.
Let us say that we had only three bottles to test, then how would be go about that?
- Feed Rat 1 from bottle 1 and 3
- Feed Rat 2 from bottle 2 and 3
- If Rat 1 dies, then we know that bottle 1 is poisoned.
- If Rat 2 dies, then we know that bottle 2 is poisoned.
- If both the rats die, we know that bottle three is poisoned.
Rat 1 dies: Rat 1 drank from bottle 1 and 3, and hence if it dies then there is a possibility that
- Bottle 1 or Bottle 3 is poisoned.
- But if Bottle 3 is poisoned then Rat 2 also must die, because Rat 2 also drank from bottle 3.
- But Rat 2 is still alive, hence bottle 3 is not poisoned.
- Which means bottle 1 is poisoned.
Rat 2 dies: Rat 2 drank from bottle 2 and 3, and hence if it dies then there is a possibility that
- Bottle 2 or Bottle 3 is poisoned.
- But if Bottle 3 is poisoned then Rat 1 also must die, because Rat 1 also drank from bottle 3.
- But Rat 1 is still alive, hence bottle 3 is not poisoned.
- Which means bottle 2 is poisoned.
Rat 1 and 2 both die : As we saw in the above two cases, the only way both the rats can die is, if they drink from the same bottle. Hence, bottle 3 is poisoned.
Seems pretty simple. It looks like we need to feed each rat a different unique combination of bottles and decode by the above logic. Based on the death of rats.
The only problem is to identify how many rats and what unique combination for each rat?
A similar property is exhibited by binary representation of a decimal number. Each decimal number has a unique binary representation.
Let us find out the answer to how many first and then we will try to solve for unique combinations. We know that 1 bit can represent two unique numbers, similarly 2 bits can represent 4 unique numbers and so on, 3 bits can represent 8 unique numbers and so on.
The minimum number of bits required to represent K unique numbers is ceiling of log2K. Hence, for 15 numbers we need ceiling of log215 which is 4.
So, we need four rats to find out which bottle is poisoned. Now the problem is to find what combination of drinks each rat should be fed.
Let us understand it with the below diagram for 7 bottles.
If you try to verify each column in the above image, the first column is a binary representation of the label 1. Similarly column 6 is the binary representation of the label 6, and column 7 is the binary representation of label number 7.
Also, we have our lab rats ready for testing. Each of the row represents a unique combinations of numbers. Let me explain this a bit more.
Each row contains several zeroes and ones. The ones mean that the corresponding bottle is chosen, zero means the bottle is not chosen. The three rows are completely different combinations.
- If we feed Rat 1 with the bottles labeled (1, 3, 5 and 7) and it dies then we know that one of these bottles is poisoned.
- At the same time if we feed Rat 2 with the bottles labeled (2, 3, 6 and 7) and it dies, then we know that one of the bottles which is common for Rat 1 and Rat 2 is poisoned. Hence, we can narrow our investigation on bottles 3 and 7 because they are common among Rat 1 and Rat 2.
- Now let us feed the Rat 3 with bottles labeled (4, 5, 6 and 7) let say that this rat didn’t die. This means that none of the bottles labeled 4, 5, 6 and 7 are poisoned. Which also means that 7 is not a suspect any more. So by step 2 the bottle labeled three is poisoned.
So the process is simple, represent the label numbers with their binary representation and then feed the rats. Wait for one hour and check which all rats died.
If rats K and L died then look for the column where the cells in row K and L are 1, the bottle represented by that column is poisonous.
Suppose in the above case all three rats died, In that case we can see that the bottle with label 7 is poisoned.
If Rat 1 and Rat 3 died, in that case the bottle with label 5 is poisoned.
Hope you enjoyed this post, if there is some confusion, let me know in comments and I will try to add more details.