You have 1000 wine bottles, one of which is poisoned. You want to determine which bottle is poisoned by feeding the wine to the rats. The poisoned wine takes one hour to work. How many rats are necessary to find the poisoned bottle in one hour?

We need minimum 10 rats to determine the poisoned bottle.
Because
= 9.96 rounded off to TEN.
Here is how it works:
We number the bottles from 1 to 1000 and write their corresponding binary numbers on the bottle.
Each bottle will have a binary number with 10 place digits since 2 to the power 10 = 1024.
Now, each rat is assigned a placeholder in the binary numbers so formed.
Rat 1 is assigned binary place 1.
Rat 2 is assigned binary place 2.
Rat 3 is assigned binary place 3.
and so forth and so on...
Each rat is given a sip from the bottle if the number on the bottle at the binary place assigned to him is 1 otherwise if it is 0, it doesn't take a sip.
Now for a bottle number 28 i.e 0000011100, Rat 3, Rat 4 and Rat 5 take a sip from that bottle. This way each rat takes(or not takes) a sip from many bottles depending upon the binary number (0 or 1) appearing against his assigned binary place on that bottle.
Then we wait for an hour and to let rats die. (Sorry PETA!)
Imagine Rat 3,5,6 & 8 died. It means poisoned bottle would be:
(10) (9) (8) (7) (6) (5) (4) (3) (2) (1)
 0 0 1 0 1 1 0 1 0 0 = 0010110100 = 180
Hence bottle no. 180 was poisoned.
(NOTE: This method can be used for 1024 bottles. 1023 bottles are numbered and 1 bottle is left un-numbered. If in the end, no rats die the poison is present in 1024rth bottle though the odds of that happening is 1/1024 = 0.0009765625)

Keep  going with that, and you'll find that for  rats, we can  test  bottles if we have 2 hours (assuming the  constraint that it takes an unknown amount of time up to 1 hour for the  poison to take effect).  And going back to the problem at hand, that means with 2 hours and 1000 bottles, and the poison taking 0-1 hours to kill a rat, that we'd need 7 rats.

Comments