Bram's Nerd Rage: The Poisoned Drinks Problem
I don't know if the author of this video was trying to troll everybody by posting a question which the entire comments section would fail to make a decent answer to, but my nerd rage has now been invoked:
For the problem statement and a not so great solution, watch the video. Here’s my explanation of a better solution.
The total number of drinks is irrelevant, what matters is that it’s a big number and you’re trying to optimize the average tests/drink. The trivial solution is to test everything at a rate of 1 test/drink. The solution given in the video is to test a group of four, if it comes up negative mark those all as safe and if it comes up positive test them each individually. This is improves the rate to about .59 guesses/drink.
The big thing everybody in the comments is missing is that if you test ABCD and it turns up positive then you test A by itself and it turns up positive you have learned precisely nothing about B, C, and D so you should throw them back in the pool and repeat the procedure. You can add in the trick (which some commenters did notice) that if ABCD is positive and A, B, and C are negative you can mark D positive without testing it. Using these tricks results in this procedure:
Test ABCD. If it comes up negative, mark them all safe. If not, test A. If it comes up positive, mark it poisoned and throw B, C, and D back in the pool and restart. Otherwise test B. If it comes up positive throw C and D back in the pool and restart. Otherwise test C. If it comes up positive throw D back in the pool otherwise mark D as positive.
Because this restarts at varying numbers of steps to evaluate how well it works we have to take a weighted average for each of its cases. Each gets a value of their guesses/drink and a weight of their probability times the number of drinks they figure out. (Yes the number of drinks figures into two of those values.) I’ll spare you the number crunching. It winds up under .51 guesses/drink.
But we can do even better! We can change the process to this:
Test ABCD
If negative, mark everything safe. rate 1/4 weight .9^4*.1*4
Otherwise test AB
If negative test C
If negative mark ABC safe and D poisoned. rate 3/4 weight .9^3*.1*4
If positive mark AB safe and C poisoned. rate 3/3 weight .9^2*.1*3
Otherwise test A
If negative mark A safe and B poisoned. rate 3/2 weight .9*.1*2
Otherwise mark A poisoned. rate 3/1 weight .1
Again I’ll spare you the number crunching but it works out to about .49 tests/drink.
This may still not be an optimal solution. You can vary the number of things in the starting group being tested and the number you recurse down to if it turns up positive. You can even pull in new things not in the initial group in later rounds of testing. But I’ve done enough number crunching for now. If anybody does a more exhaustive analysis or even just finds a better solution I’ll link to it from here. The interesting general question is what the sizes of subdivisions should be as a function of the probability of each drink being poisoned. Euler’s constant probably factors in there somewhere.
Update: I did some further number crunching and found that trying 5 on the first guess works a bit better following this procedure:
ABCDE
(false) rate 1/5 probability .9^5 number 5
(true) AB
(false) C
(false) D
(false) rate 4/5 probability .9^4*.1 number 5
(true) rate 4/4 probability .9^3*.1 number 4
(true) rate 3/3 probability .9^2*.1 number 3
(true) A
(false) rate 3/2 probability .9*.1 number 2
(true) rate 3/1
That results in a rate of .478 tests/drink. One might guess that starting with 7 would work a bit better because the first test is closer to 1/2 in probability but there seem to be quantization problems where the later tests get rounded off to more unpleasant numbers. The theoretical limit is about .468 tests/drink and for an explanation of that I’ll hand the microphone over to ChatGPT:
