Tuesday, May 11, 2010

7 Bucket and Poison Problem

There are 7 buckets with water, and one of them is poisoned. You have infinite number of flies, and if you put a fly in poisonous bucket, it will take seven days to die. You need to send your friend a non-poisonous bucket in 1 week, and also you need to find out which bucket is poisoned. How many least number of flies you need to it? and how do you do it?

1) One answer would be, You need one fly for this.
How?  You put the fly in any one of the bucket, and if it dies in one week then it is the poisonous one, and send any one of the other 6 to your friend, and if fly does not die, then its non-poisonous, and you need to send this to your friend and since you have sent to your friend in one week, now take your time and repeat to find out which has the poison with the same fly.

2) Since first answer may be ridiculous, the second answer would be using 3 flies.
How? You need to number the buckets from 1 to 7 in binary and then assign one bit for each flies, and dip the fly in those buckets which has the corresponding bit set in the bucket number in binary, after seven days, if the fly dies consider it as 1 otherwise 0, and get the binary number for bucket which contains the poison.

No comments:

Post a Comment