# Number Theory Word Problem - Rats and a Bottle of Poison

#### khalidh223

##### New member
You are an evil genius. You have acquired 8 bottles of “poison”, except, disastrously, 7 are fake poison and only 1 is really poisonous. Your master plan to take over the world requires you to identify the poison by tomorrow. You have a small collection of very expensive rats, which you can use for testing. You can give samples from a bottle to multiple rats simultaneous, and a rat may receive samples from multiple bottles. Suppose you give samples in some combination to k rats and then you then wait for a day to see which ones die. Obviously you can identify the real poison with 8 rates (one bottle each), or even with 7 (one bottle each, one unused bottle; if all rats survive then the leftover bottle is the poison). But how many rats do you need to identify the poison? (Make k as small as possible.)

I am having trouble finding what k is, and how to show that there isn't a number of rats that can be less than k.

#### LCKurtz

##### Junior Member
You haven't said how quickly the poison works. If you have time, just feed samples to one rat sequentially until it succumbs. Or if you don't have time for that, maybe to a binary search if you have time. 4 samples simultaneously to one rat will determine which 4 are good, then 2 of the potentially bad ones etc. Seems to me like 3 rats worst case.

#### khalidh223

##### New member
You haven't said how quickly the poison works. If you have time, just feed samples to one rat sequentially until it succumbs. Or if you don't have time for that, maybe to a binary search if you have time. 4 samples simultaneously to one rat will determine which 4 are good, then 2 of the potentially bad ones etc. Seems to me like 3 rats worst case.
The question says that I would have to know by tomorrow, so I would not have time to test again. Are you saying that k = log2(n), where n is the total number of bottles? If so, why isn't k less?

#### Jomo

##### Elite Member
Yes, it is true that the OP did not mention how quickly the rats die but did say you wait a day to see which one dies. I suspect this means you dish out the poison in minutes and then come back to check on the rats the next day. Initially I thought your binary method was the solution but now I do not know?

#### khalidh223

##### New member
Yes, it is true that the OP did not mention how quickly the rats die but did say you wait a day to see which one dies. I suspect this means you dish out the poison within minutes and then come back to check on the rats tomorrow. Initially I thought your binary method was the solution but now I do not know?
I would have to know within a day, meaning I can't test again once I've given out the bottles to the rats. Also, how I would implement the binary method you are talking about?

#### Dr.Peterson

##### Elite Member
Since you have only one chance, you want to be able to tell from which rats die after being dosed once, which of the bottles is poison.

Rather than a binary search, which takes multiple steps, why not use binary numbers? Can you see how?

#### LCKurtz

##### Junior Member
Maybe it's a trick question. Just use your original idea and give each rat a dose from a different bottle. You only lose 1 rat and the others are unaffected, good as new.

#### Dr.Peterson

##### Elite Member
The question says that I would have to know by tomorrow, so I would not have time to test again. Are you saying that k = log2(n), where n is the total number of bottles? If so, why isn't k less?
Using the binary number (well, numeral) method I suggested, the answer is indeed 3 rats (and the log, in general). Have you seen how yet? You can prove this is the minimum by thinking about information content. How many possibilities can be distinguished by k true/false facts?

#### Jomo

##### Elite Member
Dr Peterson, can you please write up your solution or if you prefer give us a hint as I am not seeing this binary number method. As always, thank you!

#### lev888

##### Full Member
Dr Peterson, can you please write up your solution or if you prefer give us a hint as I am not seeing this binary number method. As always, thank you!
My solution is probably similar:
Line up 3 rats - 3 binary bits.
Label the bottles from 0 to 7.
Give bottle n to those rats whose bit is 1 in the binary representation of n.
E.g. bottle 2 (010) goes to rat 2, bottle 7 (111) is tasted by all 3 rats.
Dead/alive rats will indicate 1s/0s of the number of the bottle with poison.

#### Dr.Peterson

##### Elite Member
Number the bottles 0 through 7, and write them in binary. Number the rats 1, 2, 3. Give substance n to each rat corresponding to a 1 in the binary representation of n. For example, that substance in bottle 5=101 is given to rats 1 and 3.

Then see which rats die; write a 1 for a rat that dies, and 0 otherwise. The number you write is the number of the bottle containing poison, because that's the substance that was given to exactly those rats that died.

#### lev888

##### Full Member
Just finished reading "Children of time" by Tchaikovsky, where intelligent spiders built computers out of ant colonies.

#### Aliabla

##### New member
Just finished reading "Children of time" by Tchaikovsky, where intelligent spiders built computers out of ant colonies.
Is it just me or is this off topic?

#### Jomo

##### Elite Member
My solution is probably similar:
Line up 3 rats - 3 binary bits.
Label the bottles from 0 to 7.
Give bottle n to those rats whose bit is 1 in the binary representation of n.
E.g. bottle 2 (010) goes to rat 2, bottle 7 (111) is tasted by all 3 rats.
Dead/alive rats will indicate 1s/0s of the number of the bottle with poison.
Math is beautiful! Thanks