This blog is exclusively for GCT CSITA students. Contact us at 'gct.csita@gmail.com'.
Saturday, August 9, 2008
Milk and Poison
You have 15 bottles of milk and 1 bottle of poison. 4 persons can be tested on, just by giving one sample to each. You have to find out which bottles contains poison. Either all or no one or any 3 or any 2 or any 1 can die in any combination.
There are 2 possible solutions..... 1. If no time constraint is given,we can use the binary search technique.i.e dividing the bottles by 2 at each stage and proceeding with the optimal one........... 2.If there is a time constraint,assign all the bottles with no.s from 0 to 15 and use binary representation pertaining to those no.s such that the persons p0 to p3 consume the samples from each bottles only if the corresponding bit is 1. We identify the poison bottle by examining the persons i.e if po & p1 die, the 3rd bottle is the poisoned one...........
3 comments:
There are 2 possible solutions.....
1. If no time constraint is given,we can use the binary search technique.i.e dividing the bottles by 2 at each stage and proceeding with the optimal one...........
2.If there is a time constraint,assign all the bottles with no.s from 0 to 15 and use binary representation pertaining to those no.s such that the persons p0 to p3 consume the samples from each bottles only if the corresponding bit is 1. We identify the poison bottle by examining the persons i.e if po & p1 die, the 3rd bottle is the poisoned one...........
First split that 16 into 8 and 8.
Take sample from first 8 and give it to a person.
If he dies then split it into 4 and 4 and this should be continued.
if not then split the next 8 into 4 and 4 and do the same procedure with the sample from the first 4 bottles.
This will be continued till a single bottle is encountered.
we can solve it by divide and conquer method... we will find the poison in the fourth step...
Post a Comment