Just want to acknowledge that this is simply one method more efficient than the worst case scenario of testing every one individually, no reason to think this is the most efficient. Already got a few comments on how you actually wouldn't need to test every drink in each individual group of 4 because a small percentage of the time you'll have 3 safe drinks in a row, meaning the 4th one is definitely poisoned and yes that would reduce the number of tests by a little bit more. Feel free to comment some other suggestions!
zachstar
mix them all together. the dilution brings the toxicity level down to a non lethal dose. 6/16/2023. I am surprised at all the replies to my post. To set things straight, this is meant to be a "sarcastic" response to the problem, not a solution.
bbhrdzaz
They were both poisoned. I've spent the last few years building up an immunity to iocane powder.
bug
It’s cool that despite it seeming like a medical and math problem, this is basically explaining array/database search algorithms
birubu
I’m surprised Eulers number didn’t show up here after the Eulers number Video convinced me that it’s everywhere haha
obibellowme
3:33 You don't have to test all four drinks. If you test the first 3 drinks and they are safe you know the last one WILL have poison in them because otherwise the group would have already been removed in the previous group. However if you test any drink to be poisonous you have to test all of them because there can be multiple poisonous drinks in a group. This means that the actuall number of tests is not 344 but less.
yzbrian
"Any drink has a 10 percent chance of being poisoned" is a different case than "10 percent of all drinks are poisoned". In the latter case, the number of tests would be lower on average, and I think it should be easy to understand why.
Lovuschka
Darnit. And here I was thinking about how I was gonna get to enjoy a whole video dissecting the game theory of a battle of wits between a Sicilian and a masked swordsman.
Inconceivable.
ZarHakkar
This is called the "Binary Search Algorithm" in computer science. It can be used for finding an item in a sorted list, and ad-hoc versions of binary search are used in bug testing to eliminate large chunks of the software from analysis when something goes wrong. I believe it can also be used for approximating the solution to a square root.
cerebraldreams
Here from 2021, I wish my school knew this when it was doing pooled Covid tests. An application of this problem that I would be pretty confident that you didn’t foresee.
tau_
I was honestly expecting a recursive algorithm where you then split the poisoned groups into a certain group size and test again.
I'm guessing that the poisoned concentration remaining would always be too high to be more efficient than running in n time. Would have been good to have that explained in the video.
graham
All of them are poisoned. Just bite the giant in his eye for being a liar.
ianirizarry
Wouldn't even less tests be needed, if you apply the same principle more than once? Instead of testing each of those remaining drinks, you could group them again in another way and then test those other groups. Of course the percentage will be much higher now, as each group of the first step had at least one poisoned drink.
skyscraperfan
3:56
You don't have to multiply with 4. 3 tests per group should be enough at max. If atleast one is poisoned, and out of 4, 3 are safe, the 4th has to be poisoned. Right?
sasimitra
whew, we have a test machine. i was afraid we had to taste them.
Arboldenrocks
When doing the split in half search method, your initial steps are all basically guaranteed to come back as poisoned, therefore doing them is redundant. This method effectively skips ahead to the point where there is a greater than 50% chance that a result will come back clean, meaning you’ll start eliminating groups right away.
fakjbf
I’m pretty sure I have a better solution than the one presented; however, I can’t verify how many tests it would take. I’m also sure that if this indeed takes fewer tests than the solution offered, than this is still suboptimal, finding an optimal solution might be NP.
Note: lower down there is an even better algorithm.
First, we divide into groups of 7. This was about a chance of 50% to have at least one poised drink. This is how we want every test to be. Try to make the test fail or succeed with about a 50/50 chance, this way we reduce the expected entropy the most. If this group of 7 is poisoned, we then want to check a subgroup of 3 of those, which again has about a 50/50 chance of being poisoned.
If this subgroup is poisoned, we will check all 3 individually but note, if the first 2 doesn’t contain a poisoned drink, the third one is guaranteed to be poisoned and doesn’t need checking. Then we check the remaining 4 together to determine if those still need checking.
The other 4 we just do a 2/2 I think.
The lower-bound on the amount of the average amount of tests is 1000 × (-log2(p)*p + -log(1-p)*(1-p)), as that’s the number of bits of entropy we have.
EDIT: I think I have found a more optimal but still “easy” solution
We start with the initial 1000 drinks, and take 7 of those and test them together.
If they come back safe, we can grab another 7 and start again.
If they come back as poisoned we test 3 of them again.
When these come back poisoned, we no longer any reason to believe any of the remaining 4 drinks are poisoned and can put them back with the untested drinks. For the 3 drinks, we test 2 of them individually and when the one comes back as poisoned we place the untested ones also back with the original drinks. If both come back negative, we know the 3rd one is poisoned.
If the 3 don’t come back poisoned, we know they are in the remaining four. We first test 2 of those, if they aren’t poisoned we know the poisoned one is in the last 2, else it’s in the 2 we just tested, and we place the last 2 with the untested ones.
Finally, we test 1 of those drinks, and if it’s poisoned we place the last remaining drink back with the others, otherwise we know the last drink is poisoned.
EDIT 2:
This new algorithm will have for each test of 7:
be harmless with 47.83%
be harmfull with 52.17% and will on average:
do 2.81 tests and place 3.34 drinks back on the untested pile.
Which means that in on average 2.46 tests and 1.76 returned or 5.24 successfully tested. The expected number of tests is then 1000/5.24*2.46 = 469.6, which is very close to the optimal 468.9956. I didn’t check for when the remaining drinks is less than 7, but that’s not going to change the number of tests that much I assume.
Kroppeb
2:36 - "We can just discard those, because there's no poison in any of them"
unknownuser
EDIT: not only did I slightly misunderstand the problem, Robbe Pincket already came up with a similar, better solution below.
Paused at 0:55, I think I'm gonna approach this from an information theoretic perspective. Your goal is to gather the most information possible from each test, which on average will be P*log(P)+(1-P)*log(1-P) which is maximized when P=0.5, so since in the first instance P=0.9^n the closest integer is 7. So take the 1000 cups and divide into 7s, put a mixed sample from each group into the machine (142 groups of 7, one remainder group of 6 means 143 trials) and you expect to be able to declare about half of your drinks safe. Then you're left with the danger half, and the probability of any one drink being bad has doubled. So now you divide randomly into groups of 3. Now you have to do 167 tests, and again you expect to declare half safe. Now your probability is gonna be 0.4 of any drink being bad, grouping them doesn't improve your information so you run tests individually until you find all 100 poisoned drinks, at which point you can stop. Assuming everything worked out as expected so far, you have 250 suspect drinks and I think you can expect to find the poisoned one after on average 195 tests. So that's 505 tests in all to find all the poisoned drinks. That's not a rigorous estimate for the expected number of tests just a principled guess really.
So my guess is in general divide the log of 0.5 by the log of the fraction of the remaining suspect drinks which are safe, pick the nearest integer and divide into groups of that size for testing.
Fuck that took longer than I thought. How did I do?
tombackhouse
I agree that poisoned drinks indeed are a problem.
