Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There 1,000 buckets, one of them contains poison, the rest of them are filled with water. They all look the same. If a pig drinks that poison, it will die within 30 minutes. What is the minimum number of pigs to you need to figure out which bucket contains the poison within one hour?

share|improve this question
    
Does the pig die exactly 30 minutes later or at any point between the moment he drinks and 30 minutes? –  Jorge Fernández Dec 31 '13 at 21:53
    
You should reword the title so that it gives a better indication of the question you have in mind. –  mtiano Dec 31 '13 at 22:09

3 Answers 3

Assuming pigs can't share buckets:

If a pig drinks a blucket it must wait 30 minutes to drink another one. Otherwise we don't know which one killed him. That means each pig can only give information about 2 buckets. So with 499 we can only get information from 998 buckets. If none of them are poisonous either one of the remaining could have the poison. However with 500 pigs we can get info on all of them.

share|improve this answer
    
This seems right. The key statement here is that each pig can only give information about 2 buckets. –  Newb Dec 31 '13 at 21:54
    
Actually without sharing bucket's it's right, sharing buckets it's wrong. –  Jorge Fernández Dec 31 '13 at 21:56

1 pig drinks from 500 buckets, then we wait 30 minutes; if it dies you need other 499 pigs, to check 499 buckets among the first ones; if it doesn't die we need other 498 pigs which together with the first pig can check the other 499+1 buckets. So we need at most 500 pigs.

share|improve this answer

You can do it with $10$ pigs, based on the binary representation of a number. Mark the pigs $1, 2, ..., 10$. Given bucket number $n$, write $n$ in binary; every time the $k$th digit is $1$, have pig #$k$ drink.

Wait for pigs to die. Form the appropriate number, putting $0$'s for every living pig in the appropriate place, and $1$'s otherwise. The number formed marks the bad bucket.

Note that I'm assuming that the pigs can drink from a lot of buckets quickly, and that more than one pig can drink from a bucket.

share|improve this answer
1  
Wouldn't this take longer than the required one hour? –  Newb Dec 31 '13 at 21:53
1  
but it says within 30 minutes –  Jorge Fernández Dec 31 '13 at 21:53
1  
@Newb I'm assuming that the pigs can drink from a lot of buckets quickly, and that more than one pig can drink from a bucket. –  T. Bongers Dec 31 '13 at 21:56
    
@T.Bongers I think I'm seeing it come together. Congratulations then, this answer is brilliantly concise, and I'm stunned by your (immediate) intuitive solution. –  Newb Dec 31 '13 at 21:58
2  
Can't you do it with 9 pigs? You have two 30 minute intervals. so you can do it first with 2^9=512 subsets. Then if no one dies, try again with the remaining 498 buckets. –  Jorge Fernández Dec 31 '13 at 21:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.