The Poisoned Drinks Problem 

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!

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.

They were both poisoned. I've spent the last few years building up an immunity to iocane powder.

It’s cool that despite it seeming like a medical and math problem, this is basically explaining array/database search algorithms

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.

I’m surprised Eulers number didn’t show up here after the Eulers number Video convinced me that it’s everywhere haha

"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.

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.

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.

All of them are poisoned. Just bite the giant in his eye for being a liar.

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.

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.

whew, we have a test machine. i was afraid we had to taste them.

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.

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.

Thanks for the explanation. I'm a med student and when they explained it to me in lab I didn't quite understand it.

I agree that poisoned drinks indeed are a problem.

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?

My Intuition says 469 Test is the best. I calculate (-log2(10%)*10%-log2(90%)*90%)*1000=469 bits of entropy

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?

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.

Just wanna say thanks for all these videos, they're consistently brilliant, keep it up my man it's greatly appreciated :'D

There is a quicker way: So based on conditional probability each one of the 4 drinks has a 29% chance of being poisoned. Now testing in grouos of 2 would mean there is a 50% chance both are clear. And you safe 1 test. If not you test one of the two and if clear the last one must be poisoned which would mean you did 2 tests for 2 glasses. If it is poisoned you must test the last one too and you did 3 tests for 2 glasses. Your expected number of tests however would be 1.85 tests for 2 glasses. An small improvement of 25 tests.

I would go with this method: test all, if the mixture is safe, done, if the mixture is not safe, divide into 2 equal groups and test that group the same way. In the worst case with p poisoned drinks and n total drinks, I'm checking only on the order of p*log(n/p). [Edit] I tested this on python and this method tends to do better than zach's method on low percentage of poison, but quickly gets worse and is actually worse than testing all drinks one by one for the 30% case. [Edit2] I optimized my method by only testing the mixture if there is at least 50% chance if it being safe, otherwise, I skip this and split that group into two. This method is better on average and doesn't fail too much when the percentage of poisoned drink gets high.

I feel like there should be a better way to do this. I expected that after the first elimination we'd do something similar with the leftover drinks. rearrange them into new group using the new prediction toxicity percentage, continuing this process until the predicted amount of required tests would be higher than the leftover "just test them individually" amount.

Wouldn't it be better if we arranged all the cups to a square and check each row, then check each column of a row with poison present in it? I checked the math. I'm not sure tho.

That first place came in clutch and gave me my bingo! Keep up the good work Marley!

Get 1,000 volunteers. Offer them each $1 to take a drink from a cup. If 10% of the cups are poisoned, you’ll have only spent $900 to safely determine which ones are poisoned.

My initial intuition is to say that after grouping them into groups of 4 and eliminating any that aren't poisoned, you're left with some amount left over. Wouldn't this just be the same problem again, but with fewer drinks? So I guess with so few drinks, the optimal group size is just 1, right? And in theory with a larger enough initial group size or large enough probability to be poisoned, testing all of the remaining drinks individually wouldn't be optimal anymore.

Make a 32 by 32 grid with all the drinks. Some spots will remain open and that's okay, but try to keep as many lines and collums with a close to average number of drinks Test every collum and every line. 64 tests You'll see that poisoned results will create collums and lines that cross over each other over specific drinks. Test those drinks individually It will add an unknown ammount of tests in this step, but I expect AT MOST 100 tests, but at least 10 tests. So, you can find the poisoned drinks with beteween 74 tests and 164 tests.

hey, this is exactly what we’re learning in my current math class! math 341, probability and statistical inference! it felt nice to be able to predict things correctly in one of these kinds of videos for once

Another great video! Love watching your content.

You can do better. Zach split them into batches of size 4, and then tested the remaining glasses individually (batches of size 1). He needed 594 tests total. If you instead split them into batches of size 7, then 3, then 1, you only need 563 tests total.

Now I can never be blamed for poisoning someone to death anymore.... haha Cheers for the good work as always. I did have a dumb idea however. Could you make a video proving why Sin(x) doesn't equal x

We had a question similar to this, with the blood samples, in an exam. We had to calculate estimated tests for different methods, ending with the group one where we had to find the optimal group count

Back when I was in high school, I was in the top math class for the school -- essentially a group that was above the 'AP' college prep classes. In taking the Honors Advanced Algebra class, I was lucky to have a quirky color-blind guy as a teacher who was one of the first to work on heat-seeking missiles back before he became a teacher. He always encouraged out of the box thinking. And he loved giving us mental problems that were quite fun. I remember a problem where we were supposed to be working at a gumball factory and wanted to reduce the amount (volume) of gum used in our solid gumballs by 50%, yet keep the balls at the same diameter. So we had to determine what the thickness of the gum needed to be to achieve that 50% reduction in gum volume. Another fun one that I can recall right now fairly vividly was the locker painter job where the locker painter got paid for how long it took him to paint 100 numbered yet otherwise identical lockers situated on a line. Obviously this painter wanted to maximize his pay, so he wanted to find the LEAST EFFICIENT PATH to paint all 100 lockers (without painting any locker more than once). So we had to come up with the work that proved which path was longest. We also had to determine on which day of the week Columbus discovered America. That was a bit different/difficult because there's a Gregorian calendar change that you have to deal with.

In fact, i think you could save some tests with this method because if you test the three first drinks of a group of four you know for sure that the fourth one is poisoned, and then you dont need to test it. Am I right?

this solution (no pun intended) assumes that the optimal way is just to split it into equal groups and then test what remains with no further splitting into smaller groups.

This method was used during the pandemic. When tests were in short supply, certain groups of people were tested using this method. Like nursing homes, army bases, and schools. Edit: labs where people submitted samples for testing often had large amounts of samples to test and would also use this method.

1:00 into it and I'd say dichotomy like, split the amount and do a test with the glasses from the first half, then if poisonous split this part in half again, and keep doing it until either you have one glass that is poisonous (to be put aside), or a group of glass that are safe (to be kept). Then proceed with the next amount of glasses you haven't tested yet, and proceed like this until all is certain. Imma make a program of that ngl

First I'd split them into groups of 4, testing each group. However, I have different plans than presented in the video in testing each group of 4. Say there are the following probabilities of each amount of poisoned drinks in a group of 4: 0.6561 chance of 0 0.2916 chance of 1 0.0486 chance of 2 0.0036 chance of 3 0.0001 chance of 4 Now, given that there's at least 1, we can divide these by (1-.6561), and we get that there is now about an 86.1% of there only being 1. In other words, if we test the first one and it is poisoned, we can test the remaining group all at once and have an 86.1% chance to save 2 tests if it isn't poisoned and only the other 13.9% chance of adding 1 test, which is well worth it. Similarly, if we've tested 2 and then found the poisoned one, we could then test the last 2 at once as there would be an even lower chance of either of them being poisoned so you'd be very likely to save 1 test, and very unlikely to waste 1 test. The last optimization I'd suggest is that we should not have to test the 4th one at all if all the first 3 come up as safe. If we use all of these, I think we'd get a good bit better average case, and be very, very unlikely to do worse than how it's recommended in the video.

The machine would display poisoned all the time, because the way you’re taking the samples will contaminate all drinks

If anyone is interested and wants to learn more about similar problems to this, this is a central problem in the maths branch called group testing. I did my final year project on it and there's some really cool problems, another being a graph with a defective edge or node

This was very nice. Thank you.

At a time when covid tests are scarce in some countries, couldn't this be a solution?

As a vampire, I do hate constantly having to test my drinks for HIV

After analysis, a binary search where we test at each level is not efficient but if we start the binary search at the level ceiling(ln(1000*p)/ln(2)) then we get the same average number of test as in the video for high percentage (> 5%) and better than the average at lower percentage (

You can actually explicitly solve for the exact probability where your suggested method fails to improve on the brute-force solution (p < 1-exp(-1/e)). This makes the minimum occur at exactly n = e, which is quite a beautiful result. This isn’t too hard to prove either, so it’s a fun exercise to run through. Even more interesting is that above a certain probability, your curve has no local minimum and simply approaches 1000 from above as n -> inf (p > exp(4/e^2)). This one is a bit tougher to arrive at but I can follow up with the explanation in a comment if anyone is interested.

Can't we use this model to test for covid-19…

Couldnt the number of tests needed be further reduced by splitting them into groups after the first test

the number you need is a little less than 344 individual tests since there will be a situation in which 3 glasses are safe so the last one is poisoned and doesn't need testing. This situation will occur in around 7% of the total groups (.9**3*.1)

Absolutely amazing!!!

My best scenario found was to put the glasses in groups of 6 (53% chance safe, 88 of 167 groups safe, 472 glasses remain), then put the remaining 472 glasses in groups of 3 (49% chance safe, 77 of 158 groups safe, 241 glasses remain), test each of the remaining 241 individually. 167 tests in phase A + 158 tests in phase B + 241 tests in phase C = 566 total tests.

General problem: Having N Samples with probability p1, ..., pN of being positive and ability to combine the Samples when testing, run the minimum number of Tests to evaluate whether each sample is positive or not. 1 Sort the samples such that p1>p2>...pN.(optional, see note*) Add S1 to "current sampling list" 2 If p11/2 ( e.g. we may have added the S1 S2 and S4 to the list as (1-p1)(1-p2)(1-p3)=0.49, (1-p1)(1-p2)(1-p3)=0.51 and pN>0.01 hence nothing else fits in the sample) Repeat 2 until not possible. 3 Test the sampling list 4. If Negative: For each Sk in current sampling list: - Assign pk=0 (clear the Sk sample) - Compute the pk for each sample in each of "previous positive sampling lists" that contains also Sk. (in particular if a previous list contains only one more sample, it must me positive hence we can also clear the list from "previous positive sampling lists") 5. If positive: If a single sample assign p1=1 ( mark the S1 positive) and stop if nothing else to test If more samples in the current list: -compute the new probabilities in the "current list". -add current sampling list in the list of "previous positive sampling lists" -repeat with step 1 *NOTE: this does not guarantee the minimum number of tests but something very close to it. The goal is to have something closest possible to 50%; or actually the smallest distance from 1/2*N at the end of for the all the N tests performed. One other approach is to create the sampling list starting with lowest probability and moving back to highest. A third approach is to evaluate all 2^N combinations and pick the one closest to 1/2 A forth pproach is to simply pick random samples until either the entire list (or the sample alone) is more the 50% positive and skip the initial sorting. E.g. We might find that S1,...,Sk is 40% negative and nothing else fits to be less than 50% neg. Similarly Sn-k, .. ,Sn is 45% negative and nothing else fits to be less than 50% neg. However there might be a Sa, Sb, .... list that is exactly 50% negative. Even the costly computing approach of finding such a list does not guarantee the minimum as it might adversely affect the next iteration. P.S. Grouping by 4 ( when 10% positive) is NOT something optimal at all we run tests with 65.6% chances of being negative and 34.4% of being positive. We have to group by 6 or 7. It is like wasting one in three tests. Then testing individually at the end is yet another waste of tests as tests performed are still more likely to be negative. The same rate of wasted tests.

My first thought was to select a group size such that the test had a 50% chance of coming back 'poisoned', on the basis that that maximized the amount of information the test would return.

This is the kind of math I want to see in school. I want to say 95% of my experience with math (probably more) all throughout high school was our teacher giving us numbers and formulas to use, and problems to solve with no real world applications. Because of that, whenever I see problems like this...... I can understand the math behind it, but I have no idea how I would get from step 1 to figuring out how to get there on my own. I was just taught in that 3 week period of algebra 2 to use this certain formula and input some numbers into said formula to get the answer I should want...... which really sucks since now I feel like I can't actually do anything with what I've learned. I'm currently in Calculus 1 atm and I feel like if I were to try and use my knowledge of math in the real world I would be completely useless.

I was surprisingly on the right track when solving this. I thought of splitting them into groups of 8 or 10. I thought that 8-10 would be more efficient than 4-5, but I guess I was wrong!

I rarely like these types of videos as I only like that which I might want to watch again some day. This video was great though so I had to like it!

Probability is so confusing but really fun as well!

Two things 1. I would love a video finding the optimal solution 2. Here is my suggestion to futher optimizing the method shown Once you have all sets of 4 glasses with at least 1 in each being poisoned then test each group of 4 individually UNTIL you test postive. Then remove the negative glasses and set aside the untested glasses and continue that on all sets. Continue to set aside untested glasses. At the end you have removed 1 poisoned glass for each set. Now you can tell how many poisoned glasses are remaining. From that you will have a new % ratio of poisoned to non poisoned glasses so refer to the chart in the video to regroup the glasses in the optimal size and repeat the process again. Also if someone understands what I'm saying and can say it more clearly please help lol

I think the optimal strategy might be very complicated. for example, depending on the outcomes of the first group, you might choose a different group size next ect.

Holy shit this is exactly what I was looking for! You're a life saver, I'll be back when I'm done!

I love that the CC said "... there is a pee chance" of the cup being poisoned.

that was a very beaultiful non linear function with a real life application!

For the 1 poison version there is a faster way. divide to 3 test first 2 groups if in the first or second group recurse on that if not recurse on the thud one. This has lower complexity. instead of Log_2(N) it is Log_3(N)

Wow… nice timing on when you released this video. Should I be looking at your more recent ones for predictions of world events?

This is similar to how you can quickly aggregate numbers using a GPU. A sequential CPU reduce 2 entries to 1 at a time, needing N time steps. A highly parallel algorithm cuts data set to half at every iteration, needing lg(N) time steps.

Covid PCR tests were also performed in patches. It resulted in positives as well as the negatives batched with them took a lot longer to confirm,

I solved the "unknown p-value" version of this problem a few years ago. Instead of imagining a fixed number of drinks and a theoretically unbounded number of tests we might run, imagine that we have an unbounded number of drinks, but a large upper limit on how many tests we are allowed to run. Our goal is to verify the status of as many drinks as possible within this arbitrary (but presumably large) number of allowed tests. The optimal strategy for rapid verification in this second scenario will be the same as the optimal strategy for verification in the first. Define the trivial strategy to be simply testing each drink, one at a time. For any possible strategy, we define a marginal reward function for any now-verified group of some size, as simply the difference between the number of tests that were conducted to fully verify that group, and the number of tests that the trivial strategy would have required (equivalently, the number of drinks in that group). For example, if we test a new group of four drinks, and verify that all are 'clean' in just one test, our marginal reward is 3. If, on the other hand, we take four tests to verify the status of just one drink (which can happen if we start by testing a group of size four, but continuously fail to find an 'all-clean' subgroup of size >=1 as we test successively smaller and smaller subgroups of that group) then our marginal reward is -3. Our total reward at any point, then, will be the sum of these marginal rewards at that point. Maximizing our expected total reward over time is a process of maximizing our expected marginal reward for each new group of drinks that we examine, updating our estimate for p (and ideal new group size) as we go. The expected reward based on some estimate for *cleanliness* p (so, our estimate for probability of being poisoned is now represented by q) is given by an interesting sequence of polynomial functions that assign reward-weight coefficients to terms in a geometric distribution (I'm dropping the zero coefficients where they arise here, but you can try to spot the pattern): E[R]_1 = 0 E[R]_2 = (1)*p^2 + (-1)*q E[R]_3 = (2)*p^3 + (1)*qp^2 + (-1)*qp + (-2)*q E[R]_4 = (3)*p^4 + (2)*qp^3 + (-2)qp + (-3)q E[R]_5 = (4)*p^5 + (3)*qp^4 + (1)*qp^3 + (-1)*qp^2 + (-3)*qp + (-4)*q E[R]_6 = (5)*p^6 + (4)*qp^5 + (2)*qp^4 + (-2)qp^2 + (-4)qp + (-5)q (. . .) Our agent chooses the optimal group size for the next group to be tested by iterating forward through this sequence, comparing the value of E[R]_n to E[R]_n+1. Once it sees that E[R]_n+1 < E[R]_n, for any group-size n, it will stop there and choose the next group to be of size n. My solution assumes that the best way to proceed from there is to "peel off" wells one at a time so that the next test is on n-1 of those n drinks. Would there be an improvement if it instead subdivided the contaminated group of n into two equally-sized subgroups and tested each of those subgroups? I'm not so sure myself . . .

Sorry, I don't know if there's some constraint that might be missing. But this can be done (using the same method) with far fewer tests. Just apply it recursively. After the first 250 tests, don't do individual tests. Instead regroup all individual samples into new groups (such that no 2 were paired in the previous grouping). Then redo the mixed tests on those 86 groups, again eliminating 34.4%.** This leaves us with ~30 groups. After more mixing and recursion, you get 10 groups. Then 3. Then 1. 250 + 86 + 30 + 10 + 3 + 1 = 380, better than 594. **Recursive grouping will not lead to exactly 34.4% since any given drink has more than 10% likelihood of being poisoned. This chance increases after each round of testing. But still, some drinks are likely eliminated (due to being safe). As stated in the video, grouping only works at lower chances. So, there could be a breaking point which the apparent chance grows high enough (due to failing tests in group) that individual tests (or some other method) becomes more efficient. In that line of thinking, it might be better to do larger groups in order to minimize the apparent chance growth after recursive testing. Not so sure about that off the top of my head.

Great interview question

Might be worth mentioning that this is called "adaptive group testing" in statistics. There is a related field called "adaptive compressed sensing", where the goal is to find out the amount of poison in each vial, given a machine that tells you the total amount of poison in an arbitrary weighted mixture of vials (linear combination). This paper describes a binary search based algorithm for adaptive compressed sensing: arxiv:1306.6239; the way it works is as follows: If there's some structure to the probability of the vial concentrations (I'll just say values to be generic), like if for example the values are a time series that changes slowly with time, then you start by coming up with a linear transformation that is likely to make the vector of values _sparse_, i.e.: most values close to zero. Call that transformation T. Now, create a vector v where the first half of elements are 1s and the remainder are 0s. Now measure the vials weighted by the vector T^-1 v, resulting in m = (T^-1 v) · x where x is the unknown vector we are trying to find, and if m is greater than some chosen threshold t, then "recurse" into the first half of the vector (i.e.: make v have 25% 1s 75% 0s). Then, do the same thing but where the second half of elements are 1s and the first half are 0s.

I’d use the quick-sort method of splitting sections in half. Grab drops from 1-500. Then 501-1000. Use the set of 500 non-poisoned glasses. Repeat for 250. 125. Etc. If both sections have poison, split again. And again. And again. Dividing by two is the best option.

We may further reduce the number of tests using the same method by applying it recursively. (ie dividing drinks in the poisoned group into groups of 2)

HEY!!!! I've been doing that for YEARS to find out which mod is corrupted when I have game crashes in my super long modlists... I had no idea it had a name!

It sounds like it would take more time to organize drinks into groups and then collect sample of each drink in group to test, and then test the drink in positive group individually, rather than test each of them individually in the first place, if the machine can output the results right away.

With that test n amount, test n-1 and then gather all of the remainders and do another 4 batch test with them (or maybe another number might be more efficient?).

This problem seems to be related to finding an irreducible inconsistent subsystem within a set of constraints of a linear program. So what do you do, if the fraction of poisoned samples is unknown? I guess you'd have to use some scheme, which uses a variable group size.

You could make a small optimization to the solution by not testing the final cup in a poisoned group with 3 safe drinks found. The odds of having a group with a specific one poisoned and 3 not is 7.29%, so we get about 18.2, or just 18, such groups. This allows for only 176 tests. Idk if it changes the optimal levels at all because I don’t want to do more math

Beside what others have said in that it isn’t the most efficient solution, it’s also mathematically unsound as it doesn’t take into account Bayesian rule and apply posterior probability when we know a test for an entire group combined is positive (new information)

Funny how you did this video right before it became really relevant as pool testing for COVID.

A better (and very easy) solution would be to do a binary search over each of the remaining groups of 4 drinks. This would allow you to test some groups with 3 or possibly even 2 tests, instead of 4. (Considering this whole thing started out describing a simple binary search, it seems silly that they just kinda forgot that whole technique for everything that follows...)

I got down to ~322 average tests needed to solve the first example. Split it up into 10 groups of 9 and 91 groups of 10. Then any positive groups of 9 into groups of 4 and 5, and groups of 10 into 5s. Then into groups of 2 and 3. Then individually.

You’ve convinced me that this approach gets a good solution. But you have not proved that this approach gets you the best solution.

I wonder if there were more than 1000 drinks if a multiple tiered group would be optimal like groups of 1000, then split that into 4 then split into groups of 1 (individual groups).

When you are at the part where you have groups that contain a poison and not, would it be beneficial to combine those groups back to a larger group and reuse the algorithm?

All I could think of was The Princess Bride and all the drinks were poisoned.

bro just divided everything and still managed to test every single glass

Mix all the drinks together, now we know all of them are poisoned. This uses the machine 0 times

I want to turn the "only one drink is poisoned" variant into a D&D puzzle. The party wants to steal an alchemist's entire supply of a specific ingredient, potion, whatever. They happen across a room where all the potions are stored in big reservoirs connected up to an automatic mixing/dispensing machine... essentially one of those fancy soda fountains. They _could_ just steal all the reservoirs, or remove them and test each one, but getting them out of the machinery takes a long time. Running the mixer/dispenser and testing what comes out takes less, but still some, time for each operation. Add in combat, a timed hazard, or some other pressing danger, and D&D's action economy will make sure players look for ways to save time and make fewer tests.

What about regrouping and test in more rounds? For instance in the group of four example, if I first test 12, 3 groups. if it is good, we save 2 tests, if not and we first 2 groups of 4 are good, we know that last four is poisoned, so it is the same running 12 first or not. If 12 poisoned, first 2 groups have at least a poisoned we have to test last as well, so we do one more. For low percentages is better no?

do you think its a good idea to use the same pipette in 1000 possibly poisened drinks? you would get 100% positive results due to cross contamination that way (except for the first few until you reach the first poisened one)

What maniac gives you 1000 glasses of water and says "some of them are poisoned. Figure it out" and just expects efficiency

This can be intuited by looking at how you can exclude the most cases with a sinle test. If you expect a test to be positive with probability p, then on average it will exclude 2p(1-p) cases. To maximize this, p needs to be as close to 0.5 as possible. This is not the same thing as minimizing total tests though, because this test can make further tests worse, as we see in case of p>0.33 in this problem. But trying to bring the probability of a test being positive to 50% is a good idea generally.

I’m surprised you didn’t mention taking the derivative of the function you derived and setting it equal to zero to find the group size. This gives you a non-integer number that you can round up for any given p-value you are interested in. tested in wolfram and it works

But how do we know that splitting them up into groups once and then testing individually is the best approach? What about grouping and then dividing into subgroups?

Finally feeling like my applied math major taught me something when instantly responding with binary search but scaling division sizes with optimized likelihood :D

I swear these videos teach me more about statistics and probability than 2 weeks of lessons at my university

If p is low, can't you iterate the procedure instead of testing each remaining sample individually? You group them in groups of n1, compute the new p2>p1 probability, and then make groups of n2 < n1. This should hopefully converge to bisection when 1 = 1/1000

This channel is awesome ❤