Number Theory Word Problem - Rats and a Bottle of Poison

K

khalidh223

New member
Joined
Oct 6, 2019
Messages
5
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.
 
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.
 
LCKurtz said:
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.
Click to expand...
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?
 
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?
 
Jomo said:
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?
Click to expand...
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?
 
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?
 
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. :)
 
khalidh223 said:
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?
Click to expand...
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?
 
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!
 
Jomo said:
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!
Click to expand...
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.
 
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.
 
Just finished reading "Children of time" by Tchaikovsky, where intelligent spiders built computers out of ant colonies.
 
lev888 said:
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.
Click to expand...
Math is beautiful! Thanks
 
You must log in or register to reply here.
Top