And the PIG Died !
Another puzzle passed on by my insane roomie(offences intended) !A man has 100 bottles having some liquid. Only 1 among the 100 bottles has poison. He has 100 pigs which he can use for finding out the bottle having poison. A pig dies in 24 hours after it is given poison. The man has to find out in 24 hours which bottle has poison. What is the minimum number of pigs that he requires to use? He can make any combination of the contents of the bottles.
Though I got the correct answer and a theoretically equivallent solution, my roomie was all for his collegue who gave a more elegent solution.
Ok He does talk sense once every thousand years !
posted by Praveer @ Tuesday, August 17, 2004
10 Comments:
I know the answer. We figured it out together, wasting time in office, remember ;) ?
Anthro :)
n pigs where n = total no of primes within N (here N= 100)
If he has to minimise the number of pigs that die on the average and in the worst case, then the answer is 7 pigs.
1. Convert all numbers from 1 to 100 into binary (you'll require 7 bits to represent them).
2. Label the seven pigs as 1 to 7.
3. Feed the liquid from bottle one to pig 1, bottle 2 to pig 2 and bottle 3 to pig 1 and 2, bottle 4 to pig 3 and so on
4. After 24 hours, depending upon which pigs die, you can get a binary number by setting the bits corresponding to the pigs that die (writing 1-7 from right to left).
5. The above binary gives the bottle with poison.
I wouldn't risk though, will use all the 100 pigs.
-- Sundar
Sanjeeth,
Fools seldom differ! I've initially thought of the prime no soln, but Praveer told me the answer is much smaller. :p
Sundar
:(
Hey Sundar,
U got the exact answer That roomie got fascinated with.
I got it thru Combinations...
Its easier to approach when u think what is the maximum number of bottles I can test with 3 pigs. And then extend it.
2 things:
1. There is something special abt this prime number approach that I'm unable to figure out but wud like to know.
2. Sundar, Just beware of roomie ! I suspect he's Y^2 = 4 a x
Forgot to tell the genaralised formula: if N is the number of bottles, p is the different states (say poison or no poison), then no of pigs or tests required is equal to ceil(log of N to the base p).
Sundar
Praveer,
You had asked why the prime number approach uses pigs suboptimally. I thought about it and this is what I feel:
With prime numbers < 100, we are actually solving a problem bigger than 100 bottles. i.e. With the set of prime numbers < 100, we can actually detect the presence of poison in a very big subset(we cant distinguish between 2 and it's powers, though) of 2.3.5.7.11...83.89.97 bottles which is way too high, but we are actually using them to detect the presence of poison in 100 buttles only which is suboptimal.
Take a simpler case. If we had 3 pigs, we can detect poison in 2 raised the power 3 = 8 bottles using the binary number approach. On the other hand, using the prime number approach, we can detect the presence of poison in 2.3.5 = 30 bottles, but not in bottles which are labeled with numbers that are not prime numbers themselves but are powers of prime numbers.
Sundar
Sundar I dont get this . you say with 3 pigs we can detect poison is a maximum of 2 * 3 * 5 = 30 bottles. But what if the 7th or 17th bottle contains poison . How do we get this. Why do you say it covers a bigger range?
Oops. I was wrong at that. I thought only that we cannot differentiate between the powers of primes, that's why I mentioned that it covers a bigger range, but a subset of that. But, I didn't think about numbers like 5, 7 etc. Sorry for that.
Sundar
Post a Comment
<< Home