Problem: There are 20 bottles filled with water, out of which exactly one is poisonous. We have to figure out the poisonous one. We have, with us, available some mice. When a mice tastes water from a bottle, it dies after exactly half an hour. We have one hour to figure out the poisonous bottle. What approach we should take. (Problem source : www.quora.com)
Solution: Each bottle can either be drunk from by a mice or not; i.e., there are two possibilities. We can interpret this as a binary number system problem wherein '1' represents that the mice has drunk from a bottle and '0' represents it has not.
Now, let us approach with a very simple but un-optimized method. Let us have 20 mice, and assign 1 mice to each bottle (1 mice will dring water from a bottle). After half an hour, one of the mice will die. Clearly, we have the culprit bottle. This solution requires 20 mice. But, we can have a better solution as discussed below. Another option can be to choose 1 mouse only. Let it drink from one bottle, wait for half an hour if it dies. If not, let it drink from next bottle. The maximum this approach can take is 10 hours, which is way more than the budget allocated. So, solution 2 is not for this problem.
To represent number 20, we need 5 binary digits. Let us number each bottle with numbers from 1 to 20 and assign binary code representing that number to the bottle. Now, each of the bottles has a unique 5 bit code. We can assume each bit representative of 1 mouse, '1' shows that the mouse will drink water from this bottle, '0' shows otherwise.
Let us take an example. Bottle '12' will have code '01100', meaning that mouse 2 and 3 will drink water from it. The code for each bottle and respective interpretation is as shown below:
Let us say, bottle 15 had poison. So, after half an hour, mouse 2, 3 and 4 will die as only these mice drank water from this bottle, with the help of which we will come to know that this bottle contained poison.
Now, let us approach with a very simple but un-optimized method. Let us have 20 mice, and assign 1 mice to each bottle (1 mice will dring water from a bottle). After half an hour, one of the mice will die. Clearly, we have the culprit bottle. This solution requires 20 mice. But, we can have a better solution as discussed below. Another option can be to choose 1 mouse only. Let it drink from one bottle, wait for half an hour if it dies. If not, let it drink from next bottle. The maximum this approach can take is 10 hours, which is way more than the budget allocated. So, solution 2 is not for this problem.
To represent number 20, we need 5 binary digits. Let us number each bottle with numbers from 1 to 20 and assign binary code representing that number to the bottle. Now, each of the bottles has a unique 5 bit code. We can assume each bit representative of 1 mouse, '1' shows that the mouse will drink water from this bottle, '0' shows otherwise.
Let us take an example. Bottle '12' will have code '01100', meaning that mouse 2 and 3 will drink water from it. The code for each bottle and respective interpretation is as shown below:
Bottle no Code Interpretation 1 "00000" No mouse will drink water 2 "00001" Mouse 1 will dring water 3 "00010" Mouse 2 will drink water 4 "00011" Mouse 1 and 2 will drink water 5 "00100" Mouse 3 will drink water 6 "00101" Mouse 1 and 3 will drink water 7 "00110" Mouse 2 and 3 will drink water 8 "00111" Mouse 1,2 and 3 will drink water 9 "01000" Mouse 4 will drink water 10 "01001" Mouse 1 and 4 will drink water 11 "01010" Mouse 2 and 4 will drink water 12 "01011" Mouse 1, 2 and 4 will drink water 13 "01100" Mouse 3 and 4 will drink water 14 "01101" Mouse 1, 3 and 4 will drink water 15 "01110" Mouse 2, 3 and 4 will drink water 16 "01111" Mouse 1, 2, 3 and 4 will drink water 17 "10000" Mouse 5 will drink water 18 "10001" Mouse 1 and 5 will drink water 19 "10010" Mouse 2 and 5 will drink water 20 "10011" Mouse 1, 2 and 5 will drink water
Let us say, bottle 15 had poison. So, after half an hour, mouse 2, 3 and 4 will die as only these mice drank water from this bottle, with the help of which we will come to know that this bottle contained poison.
I initially thought we have a timer. Then one mouse is enough. We will let him drink from numbered bottles (from 0 to 19) with frequency once in a minute. Then the poisoned bottle will be: (timeDead - 30). In the worst case, when the poisoned bottle is the last, it will be discovered after 49 minutes, which complies to time budget.
ReplyDelete