# Minimum number of objects required to figure out the issue

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?

-
Does the pig die exactly 30 minutes later or at any point between the moment he drinks and 30 minutes? – Carry on Smiling 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. – Wintermute Dec 31 '13 at 22:09

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.

-
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. – Carry on Smiling 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.

-

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.

-
Wouldn't this take longer than the required one hour? – Newb Dec 31 '13 at 21:53
but it says within 30 minutes – Carry on Smiling Dec 31 '13 at 21:53
@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. – user61527 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
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. – Carry on Smiling Dec 31 '13 at 21:58

Okay, for the pig question, there are two ways for you to only need one, and it doesn't need to die 2/3 of the time. It depends on the "type" of pig for the first one.

Since certain practicalities are not specified, I'm going to suggest for the first scenario that your one pig be a poison-sniffing pig; since pigs have sensitive noses. The pigs sniffs out the poison, and you're done.

The second scenario is a little messy, but it works: combine all of the buckets into one vat to dilute the poison. Pour the water into the buckets and give the pig one bucket. It the pig lives, then none of them are poisoned (at least for a pig), and if he dies, then all of them are: which brings me to my third option, which is to dump them all out and start over, you have all of this time and water is cheap, so quit being lazy and just refill them.

-