Number Theory Word Problem - Rats and a Bottle of Poison

khalidh223

New member
Joined
Oct 6, 2019
Messages
3
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
Joined
May 3, 2019
Messages
122
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
Joined
Oct 6, 2019
Messages
3
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
Joined
Dec 30, 2014
Messages
4,049
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
Joined
Oct 6, 2019
Messages
3
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
Joined
Nov 12, 2017
Messages
5,056
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
Joined
May 3, 2019
Messages
122
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
Joined
Nov 12, 2017
Messages
5,056
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
Joined
Dec 30, 2014
Messages
4,049
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
Joined
Jan 16, 2018
Messages
543
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
Joined
Nov 12, 2017
Messages
5,056
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
Joined
Jan 16, 2018
Messages
543
Just finished reading "Children of time" by Tchaikovsky, where intelligent spiders built computers out of ant colonies.
 

Aliabla

New member
Joined
Sep 26, 2019
Messages
37
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
Joined
Dec 30, 2014
Messages
4,049
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
 
Top