The Poisoned Drinks Problem
HTML-код
- Опубликовано: 27 сен 2024
- Sign up with brilliant and get 20% off your annual subscription: brilliant.org/...
STEMerch Store: stemerch.com/
Support the Channel: / zachstar
PayPal(one time donation): www.paypal.me/...
►Follow me
Instagram: / zachstar
Twitter: / imzachstar
Animations: Brainup Studios ( brainup.in/ )
►My Setup:
Space Pictures: amzn.to/2CC4Kqj
Magnetic Floating Globe: amzn.to/2VgPdn0
Camera: amzn.to/2RivYu5
Mic: amzn.to/35bKiri
Tripod: amzn.to/2RgMTNL
Equilibrium Tube: amzn.to/2SowDrh
►Check out the my Amazon Store: www.amazon.com...
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!
my suggestion is to bring your own drinks from now on. lol
If You split each group of 4 into 2 groups of two and test them, many of them will be clear. (Less than the 1-0.9^2 because it's now conditional probability but still some). If they come back clear, You just eliminated 2 with one test. If not, You only have to test one for the same reason as You mentioned in this comment. (Which means 2 tests per 2 glasses if the pair tests positive together, so no more than testing each one individually)
Hi zach! I was just wondering if the groups being constituted by 4 glasses has anything to do with the fact that 4 is just the next integer from 10/e=3.6788, because the probability of a drink being poisoned is 10%.
And also the probability of 1 drink being poisoned in those groups of 4 is so close to that same value.
Sir please make informational video on environmental engineering
0:16 "The question is in the most efficient way, how can you determine exactly which drinks are the poisoned ones?"
1:59 "... but THE solution is similar."
As someone who loves maths puzzles, that phrasing set up my expectations that there is some elegant construction that finds a provably optimal solution. Now I feel let down :(
The explanation of the given solution was nice and clear, but I wish it would be more clearly stated from the beginning that you are not looking for "the most efficient way" after all.
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.
yeah right, you wouldn't do that if it was your life in the line.
This the diluted mix would also be a cure for the poison (homeopathy logic)
@@tdreamgmail The problem did not stipulate that diluting the poison could not be a solution. So it remains a possibility. Some poisons in a diluted state are actually beneficial to combating disease.
You can't make assumptions about how concentrated or how poisonous the poison is. There's no way to tell if 1/1000 of a cup is still lethal.
thanks for the advice, bill cosby
They were both poisoned. I've spent the last few years building up an immunity to iocane powder.
nice "Princess Bride" reference
Ha-ha, you fool! You fell victim to one of the classic blunders, the most famous of which is “Never get involved in a land war in Asia,” but only slightly less well known is this: “Never go in against a Sicilian, when death is on the line!”
inconceivable
BreadyBogusBeButtBoiBaby you forgot about never attack Russia in the winter
Thank you for this
"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.
yes if 10% of drinks are poisoned you can adjust your group sizes as you go, and end early after finding the 100 poisoned ones
True, it becomes a binomial probability problem, with the chance that exactly 100 drinks are poisoned is fairly low
it could be more drinks also ;)
I’m surprised Eulers number didn’t show up here after the Eulers number Video convinced me that it’s everywhere haha
Honestly I bet it's in here somewhere lol.
It looks like if the number of drinks is infinite the probability of a drink being poisoned at which there is no beneficial grouping is 1/e but that might just be a coincidence
obviously if the % of poisoned drinks is unknown you deduce the percentage by testing n/e drinks individually
Me also. I thought the 37% was going to pop up.
How come this comment 1 week old while the video was uploaded just 1 hour ago?
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.
You keep using that word. I don’t think it means what you think it means.
The next video in the series is about how to win a land war in Asia.
The next video in the series is about how to win a land war in Asia.
All of them are poisoned. Just bite the giant in his eye for being a liar.
Ian Irizarry I get that reference
Ah, Ender's Game. Great book.
bro you gonna go sicko mode on ender's future bank account manager's creation?
They could be. Each has 10% chance to be poison, not there are 100 poisonous drinks.
I see youre a man of culture aswell
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.
You might be talking about a different root approximation algorithm, but the long root algorithm isn’t based on binary search. It only uses binary search when operating in any base other than binary, since there a more than two possible options that could potentially be the closest root in a step of the algorithm. Wikipedia link: en.m.wikipedia.org/wiki/Methods_of_computing_square_roots . Check under “digit by digit calculation”
@@themeralderp9615 - There may be other approaches, but I know for a fact that you can use the binary search algorithm to "search" for an answer to a square root problem.
CerebralDreams
The first algorithm for one drink is binary search, the main algorithm of the video is *not* binary search.
Binary search can be used in general on monotone functions, like sqrt, to find the value of the function in a given point.
I keep on clicking on cool videos and within the first minute, I realize it's just a video on the binary search algorithm.
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.
Based on how covid tests work, theres no real way to do this safely. "Mixing" the solutions in this case is dangerous as it risks infecting the one mixing them
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.
whew, we have a test machine. i was afraid we had to taste them.
I agree that poisoned drinks indeed are a problem.
Would you consider leaving on a red cloth regular table lamp in the bedroom and a tubular vintage oval bulb desk lamp in the office, and seeing which type of bulb burns out first after a while, "doing an experiment" ?
My Intuition says 469 Test is the best. I calculate (-log2(10%)*10%-log2(90%)*90%)*1000=469 bits of entropy
Yep, the suggested algorithm is indeed suboptimal.
I'd say entropy reasoning proves no algorithm can use less than 469 tests on average, but it's still possible the best algorithm uses more
DeepT I say the best algorithm doesn't exist because if you already know that 10% of the cups are poisoned, you've probably done it yourself and you better know which ones you poisoned. Which makes the test moot.
In the case that the drinks were shuffled completely randomly, you have an issue.
My best algo uses 526 tests on average.=]
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?
yes that is correct, but note that will only work when the first 3 drinks are safe which won't happen most of the time. This is still more efficient but you will mostly do 4 tests. If for example you find the first drink is poisoned then you still have to keep going because you have no idea if the other one's are as well.
@@zachstar if my calculations are correct, there is a 21% chance the first three are all safe.
@@zachstar There is a 21.2% chance of only needing 3 using this method, leading to an average of 3.788 for each group of 4.
326 tests in total.
But a better method with 4 glasses is to do a binary search, as this also gains advantage of glasses arranged OXOO, and leads to an average 3.681.
316 tests into total.
@@wolffang21burgers You still don't know how many poisoned drinks there are, but I'm confident that this is still better than testing each drink individually.
@@zachstar what about testing 2 of those four at a time after it's been noted as being a poisonous set.
Rather than four tests for each, you'd be doing two minimum, four maximum.
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.
It didn’t say 10% are poisoned. It said each one has a 10% chance of being poisoned. That means that it’s possible all are poisoned as well as none are poisoned.
@@WowOafus yeah, there is a 30% chance this comment is sane.
@@WowOafusWould you consider leaving on a red cloth regular table lamp in the bedroom and a tubular vintage oval bulb desk lamp in the office, and seeing which type of bulb burns out first after a while, "doing an experiment" ?
@@tacoexpressSEEDEEholeeveryones what are you talking about?
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 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.
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.
It’s better to test it in groups of 8, requiring a max of 345 tests
@@lachlanbaker2002 How do you get that number (345)? And what do you do after you test in groups of 8 (test remaining glasses individually or something else)?
If you split into batches of size 4, then 2, then 1, you need only 250+172+33 = 455 tests.
Yes actually his soloition is far from optimum. This was quite an interesting optimization problem. By recursively doing the splitting recursively with the probablity of p the optimum splitting is ln(1/p) whic is about 0.28 for p=0.1 and initial batch size of 9.5 on average for 1000 samples
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.
If you are wondering, there is a much more optimal solution that uses an average of 472.636 tests, and I can't really explain the strategy because I got this from a computer program :/. Also, there is another comment saying that the theoretical minimum is about 469 tests on average, so that is a pretty tight bound for you.
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?
yep! good catch. What I outlined is by no means the most efficient method, what you said would reduce the tests by a little more and there could definitely be other methods out there.
This yields 576 tests an average.
@@zachstar What you did did not reduce the amount of liquid wasted. The only thing it could have done was reduce the amount of tests done. You cannot reuse liquid that is mixed with a poisoned drink. Therefore, the most efficient method is to test each glass individually, at least if you want to preserve as much liquid as possible.
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.
I think there is a problem if a row and and a column has 2 poison
I believe it would take on average less Tests because you can "think Sudoku Style" and therefore guess "smartly"
Interesting way, and could be faster in optimistic cases, but would definitly fail in pessimistic ones. In a square you could end with poison on a diagonal, making every poison test you did positive, lending you not much useful information.
Mix all the drinks together, now we know all of them are poisoned. This uses the machine 0 times
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
sin pi =/= pi
Theres your proof
lmao
@@hashtagnoname3931 Ye. It stems from the fact that you will get the same number for really really small numbers of X
Check his video on the Taylor series stuff. He explains there
@@sasimitra5871 Ahh gotcha. Thank ye very much
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.
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.
It's a percentage savings, so yes. Having very large initial drinks vastly increases the time saved by this method and at say 4 drinks you would save nothing by splitting.
Interestingly, with extremely large numbers it may be optimal to split at multiple different size groups for small poison chance. For many millions you might check x at a time and then split the remainder into 4s but only for VERY small p values.
With high poison chance you're always better off checking individually because the not-poisoned chance of group size n is (1-p)^n. As an extreme example, 50% poison chance in group size 2 means a 75% chance to need to recheck them individually which is more work total.
The optimal amount of tests for 10% poisoned drinks is for any k, 0.469*k.
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)
Panacea but you don’t know which glasses fulfill that situation the first could be poisoned but so could the other three and it’s not 100 poison glasses but 10% with statistical randomness so you can’t just do it at the end
You need to consider the permutations as well. Only in the one case you actually test three safe glasses first, you can then skip the last. That propability is .9^3*.1*1/(4 over 1) (the last bit being the binomial coefficient) or around 1.8%
@@TheAgamemnon911 import random as r
def R():
return r.choice(range(10))
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 . . .
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.
2^⅓
Alternating/oscillating sequence 1+50-49+50 (mazimizing the average distance between consecutive values withing a finite bound is essentially a wave)
No idea for Columbus but Wednesday before converting i think
@@tylerduncan5908 Oddly enough, I do remember 'Wednesday' being some part of the answer. There's basically a division by 7, back to the date of the calendar change. And then you have to make an adjustment, and then do another division by 7, paying attention to the remainder.
With the lockers, I no longer remember the best solution. I know you can go from locker 1 to 100, back to 2, then back to 99, and sort of work your way to the middle, with each 'segment' getting shorter as you get to the middle. Or you can do locker 1, followed by 51, 2, 52, 3, 53,..., 50, 100 -- which are all segments of the same 'average' length. I am not sure which of those two solutions would maximize the distance traveled. The teacher also played around with the idea of the lockers being arranged in a circle (rather than in a line) as well, but we never worked that one out.
As for the gumball problem, as I recall, the 'trick' was determining the gumball void volume first, then working backward to find its diameter/radius.
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.
What maniac gives you 1000 glasses of water and says "some of them are poisoned. Figure it out" and just expects efficiency
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.
2:36 - "We can just discard those, because there's no poison in any of them"
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
Personally the way I'd solve a problem like this in the real world is quickly write a bunch of variations and benchmark them for average efficiency.
You’ve convinced me that this approach gets a good solution. But you have not proved that this approach gets you the best solution.
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 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.
Couldnt the number of tests needed be further reduced by splitting them into groups after the first test
No, because you only know that at least one - if any - drink is poisoned, not how many exactly.
Same question here
"Huh, I wonder where he came up with that number." / "...which means that in total, 65.6% of the groups are safe." / "...never mind, I got it."
2:00 we do though. You said each glass individualy has a 10% chance of being poisonous, which by definition means 1/10th of the drinks are poisonous.
No that's slightly different. Like if I told you I just flipped 100 fair coins, does that mean 50 landed heads and 50 landed tails? Saying 10% of drinking are poisoned and each drink independently has a 10% chance of being poisoned are two different things.
@@zachstar it is different from the coins - the coins are unrelated probability. The chance of flipping heads is unaffected when you flip it once. By saying you have a 50% chance of flipping heads, we really mean that if we repeat that chance experiment an infinite amount of times, halof the time we get heads. The same isn't true of these drinks - a certain number of them have been poisoned. By saying the chance of any one of them being poisoned is 10%,we really mean that if you test all the drinks 10% of them turn out to be poison. After all, if this is not the case, the drinks in fact do not have a 10% chance of being poisoned. It would be more like the coin experiment if and only if there was a larger number of drinks which may or may not be poisoned, and this is a random selection from them. For instance if he was talking about testing any selection of drinks. He wasn't though - he was talking about a single group of 1000 drinks.
DutchM I don‘t think you understand how probability works haha
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.
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
If a machine can detect 1\1000 parts of poison, that means that the simple fact of drawing liquid from the poisoned glass, using the same dropper, will partially contaminate remaining glasses, as long as you keep running the tests. As soon as contamination level reach detection range, machine will start giving you false possitives.
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)
My vague memory of Computer Science / Pstat was an algorithm like:
pick 1/e (36.8%) items as the group size, and recurse on group 1 / 2 depending on the result.
the average is better, but worst case is not
@@RobertBlair i think we are talking about different algorithms. The one i describe is a special case of the search in the video.
@@cem_kaya I think we are both talking about the One Poisoned drink out of 1000 special case.
I think your algorithm can be improved by making it fully recursive.
Imagine you started out with 1500 drinks, and the first 500 came back clean.
This case is identical to the original 1 out of 1000 problem.
But using your algorithm, instead of splitting the remaining 1000 into 333,333,334, you would split into 500 / 500, which we assumed was not optimal at the start.
My suggestion is there is an optimal ratio to use, and use it recursively on set 1 or set 2 depending on results of test of set 1.
@@RobertBlair i meanit fully recursive
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.
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)
By "discard the safe drinks" he means "drink one and serve the rest to other people we don't want to die."
It is the optimal way to do it if you only have 2 steps, but nothing proves me that there is or no a better solution with 3 or 4 steps.
It's not a better solution. It's the Lazy Solution. The BEST solution is Isolating every single cup, and going through and testing every single cup. That is the best, most efficent, and successful possible way to test them.
What this video is about, is being the most lazy, unsafe, insecure, and prone to accidents and mistakes Test.
Cause using this example, cups with poison in it.... The poison might be on the bottom layer of the liquid, not the entire liquid, so sampling just 1 tiny drop from the top does not 100% Guaranty you actually got a poison filled drop. If the drink is 1 liter, but the poison is 10% of that, that's still 90% untainted water.
There is also the chance of mistakes. You take 1 drop from every glass. Have any of you ever had a row of something, go down that row, then turn around and do something else, then turn back to the row and know EXACTLY where you left off? How about going down a list, then opening another tab or looking away, then going back to the list. Can you always find your exact same spot you stopped on? And have NEVER made a mistake or question if it was the right one? ESPECIALLY when the entire list and row is the EXACT same, no differences?
Cause remember, they don't know if they are safe or poison yet, so can't just test the one glass, see the results, then move the glass to a different group. All the glasses are in 1 group and can't be moved away till they are all collected from and all tested at once.
^ The point being, on paper, as pure numbers only, this formula actually works cause there is no other outside variables to interfere. It's just numbers, pure numbers, no other factors but numbers.
But in actual real life practice, this does not work. Using the example they give in the video, doctors using it with blood, there are many, MANY Stories about Doctors 'Accidentally' giving infected blood to people who needed a blood transfusion. Cause they mixed up Tainted blood with Untainted Blood. And it's cause of systems like this.
Is it "Faster"? Yes. Is it "Cheaper"? Yes. Is it "Safe" 100% of the time? NO! The SAFEST and 100% BEST Results, is Isolating Every single Glass. Then Test EVERY. SINGLE. ONE.
Also note in the video, he even points out it IS the best one. For 30% of less, his formula works. But that 70% of the time it does NOT work out faster or better. And worse, it requires knowing the EXACT % and there is no margin of Error.
It's an interesting Formula. In some very very small situations when you have all the knowledge in a controlled situation, it's useful. But irl practice? It's not better. It's lazy, prone to mistakes, and is just an excuse to be cheap and endanger people's lives because 'Oh, well mistakes happen'.
that dropper dipping from glass to glass triggered me as the poison would taint every drink. So some methodology needs to be sorted as the way it was shown would make virtually ALL glasses poisonous.
When you install too many mods and some are crashing your game
Me: "One of the drinks is poisoned. Your goal is to..."
Emo kid: *drinks all*
Me: "I guess that works too."
that was a very beaultiful non linear function with a real life application!
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.
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
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.
If You eliminate about 2/3 in the first round, the probability of having a poisoned drink in a test group of the same size will triple. This means a second round will eliminate only about 24% of the remaining drinks. In the third round of testing the probability of a poisoned drink will go up to nearly 40%.
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 was able to make only 488 tests. If you divide the 86 groups of four into 172 groups of two (instead of measuring each one left). Following this, you test each pair together, which in average will only result in about 33 pairs. Finally, you test each one of the remaining 66 cups individually. 250 (initial groups of 4) + 172 (secondary groups of 2) + 66 (individual cups) = 488
Where did you get 33 pairs from, the number doesn’t make sense
At 3:42, Instead of multiplying .344 by 250 and multiplying that by 4 to get 344, you could have just multiplied .344 by 1000, to get 344.
I believe there was a much simpler solution that guaranteed 100% success, that Zach seems to have overlooked.
It is possible to "code" each of the 1000 bottles. On each of them, you write the numbers 1-1000. Then, you convert its respective number into binary. Take 10 glasses (the minimum for base 2 to reach 1000) and place them in a line. Now, using the binary code, we simply place drops from every sample into the glasses that correspond with our binary code.
For example, the 13th sample will be 0000001101, so we put a drop of this into the rightmost cup, skip one, then the next two, and the rest are empty.
This way, every sample of drink will have a unique binary code we have entered into the machine. When we then put each of the glasses through the machine in order, we can then translate the code back into base 10 to find out which of the barrels/wine glasses/whatevers is poisoned.
For example, if we put our glasses in order from right to left, and the results come back as:
1) safe
2) safe
3) safe
4) safe
5) safe
6) poisoned
7) safe
8) poisoned
9) poisoned
10) safe
That translated back to a binary code of 0000010110, and leads us to our conclusion that the 22nd barrel of liquid is the poisoned one.
This is the optimal solution if only one glass is poisoned, won't work in this case bc multiple drinks can lead to a pooled test being positive.
@@ThatBulgarianGirl If we are worried about multiple, then we take every individual bottle that could possibly contribute to our binary number and repeat the process on those.
Let's say we have 0001000001.
So we take bottle 0001000001, 0001000000, and 0000000001, and we can either just toss them away because there's so few of them, or we can repeat the test on just two glasses, and create our new combination of 01, 10, and 11.
this method allows us to narrow down our suspects and determine exactly which ones are poisoned with 100% accuracy and with FAR greater speed than Zach's method.
@@tesserax8183 but each bit corresponds to about half of the drinks. If in the example case we have 10% chance of a drink being poisoned and each bit corresponds to 500 drinks, there's basically a 0% chance that any bit will be 0. The most likely case is 1111111111, which doesn't give you any information. Your algorithm is great if there are very few poisoned drinks.
@@ThatBulgarianGirl Except if it comes up 1111111111, his algorithm is going to take 500+ hits on average, whereas my algorithm will take FAR less than that in good scenarios, and in bad scenarios we can just swap over to his.
Basically, in MOST scenarios, my algorithm far exceeds his, but in WORST case scenarios, it only decreases efficiency by less than 5%, since if we pull up a 1111111111 we can just swap to his, and we've only added 10 tests to the 500 his would take.
No matter how you spin it, mine is better on average, and that's literally the point of this whole exercise: what's better on average. He says himself even, that in worst case scenarios, his own algorithm is still worse than literally testing every poisoned glass individually. That's obvious, EVERY algorithm is worse than testing each individual glass in the worst case scenarios. But we're not talking about worst case, we're talking about averages, and in that case, mine is simply better.
You could repeat this multiple times if the p value remains below 20 ish,
250 tests of four, discard the safe ones, change which drinks are tested together and repeat.
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 felt like there is another efficient way of solving this , using binary system.
Suppose a truth table for 10 digits.
It will have 2^10 i.e. 1024 different values.
Our question has 1000 samples, so 10 digit is good assumption.
Now write their binary combination on each bottle and assign a certain position to each number.
Now for first mixture of sample, use the sampled whose binary digit at 9th position is 1.
And similarly.
You'll have 10 mixtures and when a mixture shows poison
Write that position and put all zero
You'll get a specific sample or group of samples which are poisoned .
As a computer scientest I immediently went to "Binary search", which was similar to your solution
Looks like a lot of cross contamination when you only use one pipette.
I think there is a better solution to the general formula than just taking every cup in each poisoned batch. It's possible to take smaller batches from a batch to possibly get a better solution!
Wow, me from the past, I think you're on to something!
If you got an unknown percentage of poisend ones, you probably test 100 random ones first to figure out what the average percentage is.
Wait I just realized something: If you took a batch of drinks that ends up being poisoned, and then you take any subset of those drinks and still get poisoned, the status of the remaining drinks return to it's original probabiltity, meaning you can shuffle those drinks with the untested drinks and it wouldn't matter.
To anyone curious, I used a computer program to get a solution that uses about 472.636 tests on average. Which I am (sorta) proud of.
I think that the method of testing every cup would actually be more efficient than the video describes, because if we say that 30% of the cups contained poison, then there’ll have to be a point where you have found 300 poisoned cups, but that could happen before you have done the 1000th test so then you wouldn’t have to continue.
That only works if you know the exact number of drinks that have been poisoned.
If you certainly know that k out of n drinks are poisoned, you could redo the math after removing safe groups and thus reduce tests even more.
3:51 there's a way to reduce that number. Instead of testing each drink in a group of four, test for two of them, and then for one of the poisonened two.
This would also fix the problem of going over 1000 test. Imagine having two drinks, one of which must be poisoned. I'd you test for the first one and it comes out negative, that means that the other one must be positive. Same
Obviously the true solution is to get 1000 people, give them each one of the drinks, and see who dies.
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.
Holy shit this is exactly what I was looking for! You're a life saver, I'll be back when I'm done!
No tests needed. Make a shake from 100 glasses into 1 glass. Then take a small sip and see if you feel OK. Then take another sip after some time and so on until you start feeling sick. Then stop.
I think the best way for very big n would be always grouping the probes so that we as close to a 50% chance to get a positive result and repeat the process for every "poisened group". This should be the way to gain most information by doing a single test.
But that doesn't work well if you can not split the glasses into groups like that, in general when n is small and p is big
You didn’t prove that 2 stage method was optimal. You just proved that if you used that method, these are the optimal bucket sizes.
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 can divide the 1000 drinks in 11 groups and test all the groups. At least 1 group will be SAFE and you can discard it (this is the worst case scenario, chances are that more than 1 group will be safe). This gives us 11 tests and in the worst case scenario we are left with
1000 * 10/11 drinks.
Now we repeat the same process a number of times, before we get to a small number of drinks, which we can test manually.
We can calculate the number of drinks after repeating this process X times with
N = 1000 * (10/11)^ X
Since we know 10% of glasses are poisoned (thats 100 glasses), when the number N approaches 100, we can test the remaining number of glasses manually. The final number of tests will be
T = X * 11 + N
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
If there was 1000 drinks and only 1 was poisonous, it would only take up to 45 tests to find the poisoned drink.
Picking groups of 4 every time does not seem right. The group size should be dynamically chosen based on the current probabilities a drink is poisoned and not just the starting probabilities.
Poison from a drink could cling to the eye dropper and poison the next drink.
We don't know how many of the drinks are poisoned, so the most efficient way is to test each drink individually. For all we know, all of the drinks are poisoned, so testing all drinks individually takes 1000 drops. If we knew that only one was poisoned we could base on base 2, but we don't know how many are poisoned. If you split the drinks, you still need to test both sides, which will require 1000 drops in the first part of the test, and thus, it already fails. You may reduce the amount of tests, but you lose the liquid you tested which over the whole is 1000 drops before you start combining, but many more drops when you start separating.
I swear these videos teach me more about statistics and probability than 2 weeks of lessons at my university
Huh, weird. I always called this the "Finding the broken Skyrim mod" problem. 😂
Look, this is so simple. The pellet with the poison's in the vessel with the pestle. The chalice from the palace has the brew that is true. Just remember that.
0:36 wait, if i would do that how the picture does it, everything would be infected.
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
Then it turns out the testing machine was broken, and everyone dies
Wait… So this method is basically: start with X total, don’t test them all, split them in groups of n, you just have Y left, then test them all. Why don’t you then split them in groups of m?
I got a solution with 564 tests.
Split into groups of 6, 53.1% of groups will be clean, leaving 469 cups after 166.7 tests.
Split into 3s, 48.7% of groups will be clean, leaving 240.6 cups after another 156.3 tests.
Test each remaining cup, for a total of about 564 tests.
2:41 'this means we can just discard those because there's no poison in any of them'
NO you keep the ones without poison and throw the ones with poison away lmao
poor all the cups together and now the cups are all poisoned so simple
I'm glad that people understand this, because I still don't really
You could also recombine all the groups that tested positive and do the algorithm again. So, take 1000, split into groups of size k, test 1000/k groups, remove elements of those that tested negative, recombine the remaining elements, rinse and repeat. Assuming you always use the same number of elements per group (k), you can do it in 287 tests (on average) by using groups of size 9. In general, the (approximated) total number of tests: n/k * (1-p)^(-k) is optimal when k=-1/ln(1-p). You could potentially vary the group size from iteration to iteration as well, and this would probably give an even better value. [EDIT: Actually, no, you couldn't.] Fun fact: I think that the "p>30%" cutoff where the algorithm is no longer optimal is actually 1-e^(-1/e) ~ 30.78%.
You forgot that if you have a group of size n and you know that the first n - 1 of them aren’t poisoned then the last one must be poisoned
Even with all precautions what if somebody mixed the drinks? How would we know?
And if so why did they do it?
i throw the machine out the window, mix all the drinks together, declare them all poisoned. min tests max accuracy. :)
You know you were thinking about the one glass is poisoned and the other isn't thing where you have to choose 1.