Cool! My comment was featured. The way you said "this is definitely a mathematician's use of the word "trivial"" actually made me laugh out loud. Caught me there!
As a Scratch coder and a student, I almost instantly found that it kind of like the chess board puzzle, but simplified, so we make so that there a pattern of rats show the exact bottles. Rats can die or not, so we have 2^10 = 1024 possibilities, more than 1000 bottles of wine. So, my idea is number the bottles from 1 to 1000, then feed the first rat by the wine from bottles that not divisible by 2, then feed the second with bottles that is not divisible by 4, then feed the second with bottles that is not divisible by 8, and so on. Then, arrange the rats from 1 to 10, die is 1, alive is 0, you'll have the binary code. Translate it into decimal, we have the poisoned wine's number. (Actually we can solve this open problem with x bottles and y rats by this way, if 10^y >= x, so, the least number of rats to find out with 1000 bottles is 10 rats, and 1000000 bottles is 20 rats)
Wonderful YouTubians! We need your help. Here at Infinite Series, we've heard this puzzle thrown around by mathematicians before, but no one can tell us its provenance. Anyone know the origin of this puzzle??
I'm also not sure about this puzzle but I found some dates for its potential predecessors that were about weighing coins to find the fake one. There's the version with 9 coins with 2 weighings and 12 coins with 3 weighings, which first appeared (at least in print) in: E. D. Schell, Problem E651-Weighed and found wanting, Amer. Math. Monthly, 52 (1945) 42. and D. Eves, Problem E712-The extended coin problem, Amer. Math. Monthly, 53 (1946) 156. respectively.
That would work if you didn't have limited time. Here it takes 1 hour for the rat to die but the guests will arrive in one hour too. Instead you need to be a bit clever. The binary solution is correct but it's a bit devoid of the intuition behind how you get to it. It's actually based on your solution and I wrote a comment that explains is in that light. Unfortunately TH-cam disabled linking comments but if you don't mind searching for a bit you could find it. It even has colorful visuals :>
+scottydscottd Interesting point, but I think that waste would not only regard the 1s. You would waste n-1 drops for each given amount of n bottles. So in this case a drop from each of the 999 bottles that are not poisoned or almost 50ml given drops of 0.05ml each. Which is already a nice gulp to save. Beside that your alternative solution will only cost one rats live while "standardsolution" will cost considerable more almost for sure. So, you have two very good points here (thumbs up) However although your alternative solution is definitively the morally better solution, it wouldn't be more time efficient. The problem states that it takes an hour until the rat would die if it got a drop of poisoned wine. So if you're splitting 1000 bottles in half until you know the correct bottle, it would take you ten tests. Each test costs you an hour so you're done in 10 hours. The problem also states that the party you'll need the bottles for will start in just an hour. So even if your guests are happy with the amount of wine you can set free for drinking it's quite sure you'll miss most of the fun, while waiting for the results of the tests. So that's also a sidepoint to consider. Cheers ;-)
When in floor(log2(b) + 1 not equal to ceiling(log(b))??? I just realized: there's something special about that case. It's so fun that you all are collectively figuring it out in the comments!
PBS Infinite Series floor(log_2(b))+1 will be wrong when b is a power of two. For example, 1024 can be done with 10 rats, but floor(log_2(1024))+1 is 11. Using ceil(log_2(b)) fixes this.
Although, there are only 1023 non-zero numbers you can represent with 10 digits. The highest number you can represent with n digits is 2^n - 1. You need floor(log2(4))+1=3 digits to represent 4 (100). You need 11 to represent bottle 1024 (10000000000). So, floor(log2(b))+1 is correct because it accounts for the special cases when there are 2^n bottles.
Stronginthearm XXVII For 1024 bottles, you only need 10 rats. Just include the number 0 when you assign numbers to the bottles. Lets think of a simpler scenario with only 8 bottles. ceil(log_2(8)) = 3, so here's how we do it with only 3 bits (not 4): bottle 1: 000 bottle 2: 001 bottle 3: 010 bottle 4: 011 bottle 5: 100 bottle 6: 101 bottle 7: 110 bottle 8: 111
This reminds me of "Error Correcting Codes" in computer science, to figure out where the invalid bit is located. What's especially fun is that the bits that detect the error can be included in the set of bits whose error you are trying to detect. 16 bits can hold 12 bits of data and 4 bits of error-checking, since those 4 bits can work together to determine which of the 16 is wrong.
So for 1000 bottles, we require 10 rats because 2^10 = 1024 is the smallest integral power of 2 greater than 1000. We need to be able to index all the bottles with binary. So for n bottles, we require ceiling(log_2(n)) rats. For 100, this number is 7. For 1,000,000 this number is 20. Or maybe we could just use some poison testing kits or something, poor little rats.
You don't really need to use a binary representation of numbers for this, or even treat the 1's and 0's as a number per se, really all you need is a way to ensure that the subset of rats that drinks from each bottle is unique, though using binary representation probably is the most intuitive way of doing that, but nothing's stopping someone from using Gray Code for example, or you can come up with any method at all, so long as the subset of rats for each bottle is unique. After that, the logic is simple. Since rats are only affected by the poisoned bottle, and each bottle is associated with a unique subset of rats, therefore every possible subset* of (dead) rats links back to only one bottle, the poisoned one. *Well we only had 1000 bottles here, and with 10 rats there are 1024 possible subsets but yeah whatever you get the idea. :)
Some other variant questions worth considering: What do you do if not just one, but N bottles are poisoned? What do you do if some of your poison isn't 100% effective? What do you do if some of your rats are pre-poisoned by someone else? Hint: Start looking into error correcting codes.
Thank you very much for this fascinating solution, and the associated excellent presentation. Answers to your question: for 100 bottles you need 7 rats. for one million bottles, you need 20 bottles
Next time you want to give people a chance to solve a puzzle, try not to spoil it ("it has to do with binary numbers") before even telling what the puzzle is. :)
+ Yeah. With the binary numbers hint it was too easy. Without that I probably would have thought of it in terms of binary search eventually, but the hint brought me right there without having to think of any different ways to find it
Indeed though it's pretty hard not to instantly jump right there when you have such obvious binary output as live rat or dead rat. Or is that just me having done far too much computer programming that any two state system instantly becomes a sequence of 0's and 1's the moment I glance at it?
I came up with a completely different solution (took me more than an hour) but I was completely blown away🤯 on how the binary was used to solve the problem. Also in my solution only two rats dies, two bottles had to be thrown away and also the solution is lengthy..😁
As soon as you said "Binary Numbers" I figured it out :D * Give every rat a number * Give every bottle a number; write it in binary * Give every rat a drop from each bottle for which the bit corresponding to its number is 1 * After the rats have died, find the number where the nth bit is 1 if that rat died, 0 otherwise * That bottle is poisoned.
The proposed solution would only work for a number bellow 15,000 of wine bottles. Since statistically speaking you could only extract 15,000 drops (0.05 ml) out of a wine bottle (750 ml).
Hi PBS Infinite series, please correct me if I am wrong but if you are administering wine to the rats that correspond to each figure 1 in all the binary numbers 1 to 1111101000 then you will need to administer 4686 (according to my calculations) decimal drops of wine, which seems a very arduous process and I suspect will take much longer than 1 hour. May I suggest you postpone the party, get less fickle friends and use the binary search algorithm I used below, which only needs 1000 drops of wine. Apologies if this has already been mentioned or is complete bs. Fantastic videos keep it going :)
Forget time, I think with the presented approach you are very likely to make a mistake somewhere. But if replacing friends is an option, then instead of "less fickle" I propose getting friends which are risk takers and doing no tests :P now you have a party game!
Awesome! Love this new channel! This reminds me of the balance puzzle of determining the outlier out of 27 balls, given three comparative weighing with a balance. What is known is that the outlier is heavier than the other balls. Hint: The fact that 27 = 3^3 is no coincidence.
It reminds me of a very elegant video of 3blue1brown about the Hanoï Towers and their link to the binary counting system. Did I see two different haircuts? Just landed on this channel, I was kind of hoping finding one good of such. My search is over :) Thanks for the whole series!
Amazing new PBS channel! So damn good. I know many people probably wrote it already, but for 100 rats you need at least 7 rats to represent at least 100 bottles in binary, and you need at least 20 rats to represent 10^6 in binary.
The technique of halving is a similar but simpler approach. Drop feed a rat with bottles 1-500. If it dies, use that set, if not you will be using 501-1000 from now on. This is a diversification of a binary approach that would indicate the precise poisoned bottle by subsequent halving procedures: Rat 1 halves to 500 Rat 2 to 250 Rat 3 to 125 Rat 4 to 63 (or 62) Rat 5 to 32 (or 31) Rat 6 to 16 Rat 7 to 8 Rat 8 to 4 Rat 9 to 2 Rat 10 plays Russian Roulette to spot the poisoned bottle
Exactly. When she mentioned binary numbers, she gave it away. As a software developer who's quite familiar with the binary system though, I wonder if I'd have found the solution had she not mentioned the binary numbers at the start of the video. My guess is it would've taken me a long time, and I might have given up and just continued watching for the solution. ;)
24 seconds into he video and I'm like "yeah, a mathematician WOULD be the one to randomly poison a wine bottle just for math's sake" followed by "of course binary numbers are involved, binary is _everything_[1]" [1] Source: CS major, can confirm universe is a supercomputer
Follow up question answer: You need the next largest power of 2 rats plus one, so 128>100>64, so you need 2^n=128 or log[2](128). Even though you didn’t have a rat to carry the 1024 place in the original example, you also had a 2^0 at the start carrying a zero or one, instead of a “twos place”. So by this logic, you need to have the first POWER of two greater than the given number, and the power will be the answer to how many rats you need. In the case of a million, it’s 20 rats.
Enough with this finite stuff, let's talk about infinitely many rats and infinitely many wine bottles. Suppose we had countably infinitely many rats and uncountably infinitely many bottles of wine to test. Using a similar feeding strategy, couldn't I tell you which one of the uncountably many wines is poisoned because the set of all possible binary sequences is uncountably infinite?
Mathoma this may be overly pedantic, but the set of all binary sequences is not uncountable. the set of all infinite binary sequences is uncountable, but the set of all finite binary sequences is countable (proof by laziness: the first set maps to the reals, the second set maps to the naturals).
+Baby Bop But what if you have infinitely many guests, and you don't want any of them to be poisoned? (Assuming that you can't just mix the wine in the bottles to get the poison per bottle beneath the lethal dose.) (And assuming that it's possible to distinguish for every rat if it didn't just die from alcohol poisoning.)
Thank you for explaining this in such a good manner. I was always bad at math but always liked the subject. I learned to read binary from a video, damn! gj PBS you did it again. Regarding the answers - You would need 8 rats to check 100 bottles and 21 rats to check 1 000 000 bottles.
You gave a huge hint when you mentioned binary numbers being the answer. So obviously number all the bottles 1-1000 give each rat a decimal place and for each bottle give it to the rats whose decimal place would be 1 if you converted to bottles number to binary.
Newtonian estimation! Feed a drop from the first 500 to the first rat, if the rat is poisoned continue with this half, Then split again and feed 250 to a rat, if it dies continue with this half... Keep going and you will need exactly 10 rats, 1:500, 2:250, 3:125, 4:62.5, 5:31.25, 6:15.625, 7:7.8125, 8:3.90625, 9:1.953125, 10:0.9765625. This last number is less than one (and would be one if we started at 1024) so we have narrowed it down to one bottle. No need for binary, just keep splitting the bottles in two!
Since you are testing for a binary state to the bottles (poisoned/not poisoned) I wonder if this could also be applied to anything with n states by using the nth-base number representing each item. Is there any name to this method?
You'll need 7 rats to check 100 bottles, because 2^6 < 100 < 2^7 And 20 rats to check one millon bottles because 2^19 < 1 000 000 < 2^20 To put it in an other way, you can write 100 in binary with only 7 digits and 1 000 000 with only 20
Here's a different way to think about it: You give the first rat exactly half of all bottles, if it dies, you'll know which half contains the poison. The second rat is fed half of the bottles the first one was fed and half of the ones it wasn't, now by combining the information about the first and second rat, you narrowed it down to a quarter of all bottles. And so on... maybe a little less elegant but that's how I solved it (without using binary numbers directly), although it's essentially the same.
Magenta Field That's unsolved. For 2 poisoned bottles, the lower and upper bounds for the minimum number of rats needed are 19 and 43 respectively. So, it's possible with 43 rats.
Magenta Field I was talking about 1000 wine bottles. But it should hold true for 1024. If you're interested in these kinds of problems, then read about combinatorics (which deals with questions like these). This problem is also related to information theory and computer science. Here's some links related to this problem: mathoverflow.net/questions/59939/identifying-poisoned-wines/60312#60312 www.math.uiuc.edu/~z-furedi/PUBS/furedi_frankl_union-free-and-entropy.pdf math.stackexchange.com/questions/639/logic-problem-identifying-poisoned-wines-out-of-a-sample-minimizing-test-subje
I'm not sure what the solution is for N poisoned bottles and M total bottles, but it is possible to bound the number of rats. With M total bottles and N poisoned bottles, there are M choose N poison bottles. Each rat either lives or dies so it can give you at most 1 bit of information. It takes log_2(M choose N) bits of information to know exactly which N bottles are poisoned. So you must need at least ceil(log_2(M choose N)) rats.
for any number of bottles of wine, you simply need the number of bottles needed to express that number in base 2 which is ceiling(log base 2 of (number of bottles))
You could have a table of every bottle divided into sections. with time recording everytime the mouse receives a drop from each bottle in its set. you would then record the time of death for the mouse, and subsequently search for the time related to the drop taken 1 hour prior.
That's Really cool. It's basically the same method used to work with Hash Tables, which can store and retrieve information on the order of O(1). Really clever.
After thinking about it, my solution is equivalent to the one in the video, except mine is more visually intuitive. I'm gonna include some pictures: pichoster.net/images/2016/12/25/PoisonWineSolution.png Explanation: Each rat drinks from their corresponding bottles. The corresponding bottles are given by the black areas in the picture. Each rat drinks from exactly 500 bottles, so a dead or alive result will tell which half (black or white) of the bottles the poison one is. The reason this works is because with ten rats, each rat narrows down the suspected pool by half so since 1000/(2^10) < 1, you will have exactly 1 bottle left that is suspected of being poison.
PT Yamin Funnily enough, that is exactly what I first though. It makes quite a bit of intuitive sense as every rat halves the "suspected pool". Nice graphic by the way.
That's what I came up with, too. It works, and it's not the same as the solution in the video. Our solution gives every rat wine from half the bottles, whereas the solution in the video does not.
lastnameavailable326 Actually the video does, if the amount of bottles were a power of two. The fact that they aren't does however not change the method significantly.
Fantastic puzzle! Googling decoding/encoding gives me information theory. Do you have any recommended textbooks that I can use to study up (say, college/grad-level)? Thank you. ^^
Fantastic puzzle! In general, you can test up to 2^n bottles with n rats (including one bottle fed to zero rats). What I didn't think of was the binary way of seeing it, I saw it as the sum over x from zero to n of n choose x. The nice thing about this method is that it is flexible if you add some constraints, such as being able to pour at most 5 drops from a bottle (and save more wine from each bottle for your guests), where you can test up to 638 bottles and find the single poisoned one or would need an 11th rat to test all 1000. Very excited to see what's next on this channel!
I came up with a solution where I could discard as few as 40 to 50 bottles in all cases. It wasn't as clever as the binary solution, but I did have a good time trying to minimize the number of bottles discarded.
Depends on how you label the bottles, if you start with 0, it's ceil(log2(x)) with x the number of bottles. If you start with 1, it's floor(log2(x)) + 1
Just discovered this channel - looks good. I've been crap at maths my whole life - I only in the last few years grasped what numbers were about. I'm still rubbish, but that stepping stone I just mentioned (I'm sure there is a stepping stones maths problem? :P ) got me hooked. Like with the fibonacci series - it blew my mind with all the patterns of the single digit numbers in the series (repeating every sixty terms.. as well as mirroring etc). I also got my head a bit around conceptualising infinity in different ways as well (realising you can have multiple infinites). A cool thing was just taking y = (1/2)x taken to infinity and mapping it onto half of a hemisphere to get something very close to 3 arcs of a fibonacci curve (when viewed from above)... How I did I don't know, but then I repeated that pattern 60 times onto a sphere using a dodecahedron pattern, and amazingly all these curves seemed to meet at either tangents or right-angles.... but I only constructed this pattern roughly... despite my best efforts (which isn't saying much) I couldn't determine the precise equation to create such a pattern - it didn't seem to be either a fibonacci curve or y = (1/2)x, or an exponential curve either... it was looking like a curve made from an infinite series: having looked into the riemann hypothesis I thought either I'd just got that wrong, or, if it was an infinite series, then there was no way I was going to be able to figure it out... even more annoying was that the pattern of curves meeting at tangents or right-angles seemed to work with hyperspheres as well... I wills nevers knows..... :/
nice riddle, i quite enjoyed this and the hyperspheres video. just one criticism though: mentioning binary in the setup was such a huge hint that solving it wasn't quite as much fun (or trivial...).
Your first solution was my solution as well, and I see there's still six minutes left, but there're actually 11 groups possible with this method. Each rat could sip from 91 bottles, leaving 90 untested. If none of the rats die, then either rats aren't affected by the poison like we thought, or the poison was in the last 90 bottles. Ten more bottles saved!
My answer is different to the one in the video but I'm pretty sure it still works. If you label each rat A to J you can give bottles 1-10 to a single rat each. Bottles 11-55 you can give to two rats; AB, AC, AD, AE, AF, AG, AH, AI, AJ, BC, BD ... IJ (45 combinations). Bottles 56-175 to 3 rats; ABC, ABD ... HIJ (120 combos), 176-385 to ABCD ... GHIJ (210 combos), 386-637 to ABCDE ... FGHIJ (252 combos), 638-847 to ABCDEF ... EFGHIJ (210 combos), 848-967 to ABCDEFG ... DEFGHIJ (120 combos) and 968-1000 there are enough 8 rat combinations to cover the full 1000 bottles. Eg. If rats ABCDEF all die and no others you know that bottle 638 has the poison
Some say TH-cam is "broken". I'd agree. Some of the videos that get extra attention from TH-cam are, first of all, clickbaits and I understand the reasoning behind this. Back to the point: clicking on these videos is a bit of a gamble: one may never know when or if the following video has quality to it or not but if content is satisfactory then the loop goes on... Today TH-cam recommended me yet another clickbait and I fell for it. On the birght side: 10/10 one of the best gambles of my life. Thank you for the brain exercises and interesting thoughts.
Is this related to the Josephus Problem? I just watched a Numberphile episode on it that. It seemed to have a solution in binary that's really similar to this poison rat problem.
4:38 I don't get it, what does that 1 to 512 means? since you ends just using the rats at 1 or 0. I don't see how this relate to the rest of the problem
well combinations work too, nc0+nc1+nc2+.........+ncn= 2 power n and 2 power 10 is 1024, and as for the question you asked answer will be log N base 2 and nearest greater integer is the answer
To represent (2^n - 1) decimal numbers in binary excluding 0, i need n binary digits. Therefore i will need log_2(n) + 1 binary digits to represent n decimal numbers excluding 0, or log_2(n) counting them from 0 to n-1.
I think some of the comment clips were repeated, or were not from the comments being referenced. You still get a thumbs up though. I'm really enjoying this series, and so is my six-year-old daughter.
For 100 bottles it should only take 7 and for 1,000,000 it should take 20. To figure out how many rats you need, you can take the base 2 log of that number and round it up. Base 2 log of 100 is about 6.6 so rounded up is 7. 1000 is about 9.9 so rounded up is 10 and 1,000,00 is about 19.9 so 20. Another way to think about it is the amount of rats must be equal to the digits in that number when written in binary. So we could just mulitply by 2 everytime until we get above that number. 1:2, 2:4, 3:8, 4:16, 5:32, 6:64, 7:128 > 128 is bigger than 100 so we only need 7 binary digits. continue this method and you will find that 1,000 takes 10 and 1,000,000 takes 20.
Yea... there's always another solution. If you have 1000 bottles just dump all of them out mixing them together to create a delicious red wine blend and in the process you dilute the poison enough to where it's harmless.
I thought about this as sets. If you only ha D 2 rats... all you could do is assign bottles 0-500 to the first and 501-1000 to the second. This means 500 bottles are saved. But adding another rat (for a total of 3) means you can now assign 250-750, decreasing the number of wasted bottles by half. Supposing the venom is in the 600th bottle, then both the second and third rats would die. Meaning the number is in the range 500 to 750 which is correct. Each additional rat halves the uncertainty meaning saving more bottles :) Cheers!
I didn't know binary, my solution was to number the bottle from 1 to 1000; give the first rat a drop from the first bottle of every two (1, 3, ...), the second rat a drop from the first two bottle every four (1, 2, 5, 6,...). To explain this system with four bottles: if the first rat dies you can tell it was bottle 3, since it was the only bottle only the first rat drank from. For the same reason, if the second rat dies you can tell it was bottle 2, if both rat dies it was bottle one, the only one both drank from, and if no rat dies it was bottle 4 since no rat drank from it. Adding a third rat (which drinks from the first four bottle of every eight) will make you able to test eight bottles, and with ten rats you can get to 1000 (2-4-8-16-32-64-128-256-512-1024). Though I guess it's the same principle.
can anyone tell me how to find out the distance between the two corners of the cube diagonally in higher dimensions using pythagorean theorem ,given that length of each side is not a unity..?
You can find the length for the unity cube, which for n dimensions is sqrt(n), then you multiply by the length of one side, since it scales linearly with the cube. EDIT: Also i found this: www.varsitytutors.com/sat_math-help/how-to-find-the-diagonal-of-a-cube EDIT2: The general rule for a n-dimensional box with independently long sides is: Square root of the sum of the square of the sides, sqrt(/sum{side} side^2) Example: A 3- dimensional box with sides 3, 4, 5 would have a diagonal.of sqrt(3^2+4^2+5^2) = sqrt(50) And if all the sides are the same, like s, it goes like this: sqrt(n * s^2) = sqrt(n) * sqrt(s^2) = sqrt(n) * s I found all of this out myself but i'm to lazy to make a proof. It's out there somewhere if you want it though.
After the first step, i.e. feeding 100 samples to each rat, and figuring out which group of 100 bottles has the poison, you could feed 11 of the 100 bottles to each rat. If any 1 dies, you know know which group of 11 to look at. If none dies, you know it's the one which you didn't feed to any of them. If 1 dies, you take that group of 11 and feed 2 samples to each of the 3 of the rats, and 1 to each of 5 of the rats. If one of those who took 1 sample dies, you know the bottle. If one of those who drank 2 dies, feed one of the samples it drank to 1 rat, and the other one to the other. Then you know your bottle.
With 10 rats we can get 2^10 different outcomes = 1024, which is greater than 1000 and the closest number we can get to it by using only natural numbers. So if we want R rats for 100 different outcomes we would need to find the smallest natural number R, where 2^R >= 100. (I'm studying IT so I know from memory that 2^7=128 :P ) If R = 7, then 2^7 = 128 which (as above) is >= 100 and the closest number we can get to it. So, the mathematical way to find R for any desired amount of outcomes is this: R = ceiling( log_2(Outcomes) ). (Where we choose the value of "Outcomes" and we search for the value of "R".) :)
I think I figured out the question at the end. For 100 bottles of wine, I think you would need 7 rats. That is because you need a rat for each possible binary position from 0-100. 2^6 is 64, which is too low. 2^7 is 128, which is enough. For example, if you only had 6 rats, you could only encode 64 bottles of wine. But with 7 rats, you can encode all 100 (with 28 to spare!). Is that the right answer? I figured it out after re-watching the video and noticing 10 rats were needed to encode up to 1000 (aka a 10 string of binary digits). I then did the math to figure out the least exponent of 2^x so that it was >= 100.
People have given the formula in the comments section, but here's it in a form that you can actually plug into your calculator, since most calculators don't have a direct "log 2" button, but they do have a natural log button. RATS = ceiling(ln(BOTTLES)/ln(2))
(4:46) Apparently whoever poisoned the bottles also stole bottle #8. :)
Doug Rosengard nice catch
This comment should have more likes.
You mean bottle number 1000
Good eyes haha. But bottles 1-5 were also gone 😜
noticed that too
Mix all the wine together and hope that dilutes it enough that no one will die.
Hope is a funny thing my friend.
Cool! My comment was featured. The way you said "this is definitely a mathematician's use of the word "trivial"" actually made me laugh out loud. Caught me there!
@David de Kloet Well reasoned!
As a computer engineer, I almost immediately recognized the similarity of this problem to ECC correction codes.
As a Scratch coder and a student, I almost instantly found that it kind of like the chess board puzzle, but simplified, so we make so that there a pattern of rats show the exact bottles. Rats can die or not, so we have 2^10 = 1024 possibilities, more than 1000 bottles of wine. So, my idea is number the bottles from 1 to 1000, then feed the first rat by the wine from bottles that not divisible by 2, then feed the second with bottles that is not divisible by 4, then feed the second with bottles that is not divisible by 8, and so on. Then, arrange the rats from 1 to 10, die is 1, alive is 0, you'll have the binary code. Translate it into decimal, we have the poisoned wine's number. (Actually we can solve this open problem with x bottles and y rats by this way, if 10^y >= x, so, the least number of rats to find out with 1000 bottles is 10 rats, and 1000000 bottles is 20 rats)
Yup
Misread the title, thought it was the *Poisson* Wine Bottle Challenge haha
Yes, I'd like one fish wine please
4:34 there is no 8th bottle
I guess that was the one with poison. :D
8 in binary is 1000. I guess it was intentionally skipped to avoid confusion with 1,000 in base 10
Wouldn't that have caused 9 to be missing?
it's 4:32
it's 4:32
Wonderful YouTubians! We need your help. Here at Infinite Series, we've heard this puzzle thrown around by mathematicians before, but no one can tell us its provenance. Anyone know the origin of this puzzle??
Not sure about this particular puzzle by the field* was invented in 1943 by Robert Dorfman.
*Group testing: en.wikipedia.org/wiki/Group_testing
I'm also not sure about this puzzle but I found some dates for its potential predecessors that were about weighing coins to find the fake one. There's the version with 9 coins with 2 weighings and 12 coins with 3 weighings, which first appeared (at least in print) in:
E. D. Schell, Problem E651-Weighed and found wanting, Amer. Math.
Monthly, 52 (1945) 42.
and
D. Eves, Problem E712-The extended coin problem, Amer. Math. Monthly, 53 (1946) 156.
respectively.
That would work if you didn't have limited time. Here it takes 1 hour for the rat to die but the guests will arrive in one hour too. Instead you need to be a bit clever. The binary solution is correct but it's a bit devoid of the intuition behind how you get to it. It's actually based on your solution and I wrote a comment that explains is in that light. Unfortunately TH-cam disabled linking comments but if you don't mind searching for a bit you could find it. It even has colorful visuals :>
You cannot do multiple runs. th-cam.com/video/N3qmN6pYhi0/w-d-xo.htmlm3s
+scottydscottd Interesting point, but I think that waste would not only regard the 1s. You would waste n-1 drops for each given amount of n bottles. So in this case a drop from each of the 999 bottles that are not poisoned or almost 50ml given drops of 0.05ml each. Which is already a nice gulp to save. Beside that your alternative solution will only cost one rats live while "standardsolution" will cost considerable more almost for sure. So, you have two very good points here (thumbs up)
However although your alternative solution is definitively the morally better solution, it wouldn't be more time efficient. The problem states that it takes an hour until the rat would die if it got a drop of poisoned wine. So if you're splitting 1000 bottles in half until you know the correct bottle, it would take you ten tests. Each test costs you an hour so you're done in 10 hours.
The problem also states that the party you'll need the bottles for will start in just an hour. So even if your guests are happy with the amount of wine you can set free for drinking it's quite sure you'll miss most of the fun, while waiting for the results of the tests. So that's also a sidepoint to consider. Cheers ;-)
Number of rats := floor(log2(b)) + 1, where b is the number of wine bottles.
or you could just ceiling(log2(b)) ;)
When in floor(log2(b) + 1 not equal to ceiling(log(b))??? I just realized: there's something special about that case. It's so fun that you all are collectively figuring it out in the comments!
PBS Infinite Series floor(log_2(b))+1 will be wrong when b is a power of two. For example, 1024 can be done with 10 rats, but floor(log_2(1024))+1 is 11. Using ceil(log_2(b)) fixes this.
Although, there are only 1023 non-zero numbers you can represent with 10 digits. The highest number you can represent with n digits is 2^n - 1. You need floor(log2(4))+1=3 digits to represent 4 (100). You need 11 to represent bottle 1024 (10000000000). So, floor(log2(b))+1 is correct because it accounts for the special cases when there are 2^n bottles.
Stronginthearm XXVII For 1024 bottles, you only need 10 rats. Just include the number 0 when you assign numbers to the bottles. Lets think of a simpler scenario with only 8 bottles. ceil(log_2(8)) = 3, so here's how we do it with only 3 bits (not 4):
bottle 1: 000
bottle 2: 001
bottle 3: 010
bottle 4: 011
bottle 5: 100
bottle 6: 101
bottle 7: 110
bottle 8: 111
Oh PBS, you never disappoint me with these amazing channels. Thank god I arrived here at the beginning of the ride, because this channel is awesome!
This is my new favorite channel.
This reminds me of "Error Correcting Codes" in computer science, to figure out where the invalid bit is located. What's especially fun is that the bits that detect the error can be included in the set of bits whose error you are trying to detect. 16 bits can hold 12 bits of data and 4 bits of error-checking, since those 4 bits can work together to determine which of the 16 is wrong.
I saw this video when it had 1,010 views, 100 likes, and 1 dislike, and I accidentally paused it at 10 seconds.
Bow before your binary god
I only have a hexadecimal god, so I have fleventy-five reasons not to.
Well played
M.W. Vaughn my date of birth is 01/10/01 .I AM BINAR GOD
Too bad that's counted in decimal. You false god.
Do not look behind the curtain!
"Hmpf. These bottles have all been opened. Can we get some fresh ones?"
Give him the poisoned one
OMG JUST FOUND THIS CHANNEL. MORE MORE MORE
same
So for 1000 bottles, we require 10 rats because 2^10 = 1024 is the smallest integral power of 2 greater than 1000. We need to be able to index all the bottles with binary. So for n bottles, we require ceiling(log_2(n)) rats. For 100, this number is 7. For 1,000,000 this number is 20.
Or maybe we could just use some poison testing kits or something, poor little rats.
You don't really need to use a binary representation of numbers for this, or even treat the 1's and 0's as a number per se, really all you need is a way to ensure that the subset of rats that drinks from each bottle is unique, though using binary representation probably is the most intuitive way of doing that, but nothing's stopping someone from using Gray Code for example, or you can come up with any method at all, so long as the subset of rats for each bottle is unique.
After that, the logic is simple. Since rats are only affected by the poisoned bottle, and each bottle is associated with a unique subset of rats, therefore every possible subset* of (dead) rats links back to only one bottle, the poisoned one.
*Well we only had 1000 bottles here, and with 10 rats there are 1024 possible subsets but yeah whatever you get the idea. :)
I was wondering myself if binary was a necessary part of this process- this simplifies the idea down in a nice way!
Exactly! So it’s not necessary to use binary since each bottle could be linked with a single combination of rats. Still the binary method is cool too.
I can't believe someone was actually able to figure this out. That's an impressive level of cleverness,
10 PETA members disliked this video.
10 rats disliked this video))
10 rats and 4 PETA members..
U Wot M8 and 1 of them died
😂😂😂😂 we're just using them as tools.
The party starts in an hour, so I only have enough time to go through 1000 bottles of wine and give 10 rats samples from 100 bottles each
Some other variant questions worth considering:
What do you do if not just one, but N bottles are poisoned?
What do you do if some of your poison isn't 100% effective?
What do you do if some of your rats are pre-poisoned by someone else?
Hint: Start looking into error correcting codes.
Thank you very much for this fascinating solution, and the associated excellent presentation.
Answers to your question:
for 100 bottles you need 7 rats.
for one million bottles, you need 20 bottles
20rat is it???
Next time you want to give people a chance to solve a puzzle, try not to spoil it ("it has to do with binary numbers") before even telling what the puzzle is. :)
+
Yeah. With the binary numbers hint it was too easy. Without that I probably would have thought of it in terms of binary search eventually, but the hint brought me right there without having to think of any different ways to find it
Alex Knauth the first thing I thought of was binary search, but when she said we only have an hour, I got stumped
figured it out in about 7 seconds, pausing before binary numbers was ever mentioned.
Indeed though it's pretty hard not to instantly jump right there when you have such obvious binary output as live rat or dead rat. Or is that just me having done far too much computer programming that any two state system instantly becomes a sequence of 0's and 1's the moment I glance at it?
Best explanation I've come across for this math/programming challenge
I came up with a completely different solution (took me more than an hour) but I was completely blown away🤯 on how the binary was used to solve the problem. Also in my solution only two rats dies, two bottles had to be thrown away and also the solution is lengthy..😁
Coming here after reading cracking the coding interview book. Amazing explanation.
Thank you
You are doing some great videos, thank you very much for all your effort.
As soon as you said "Binary Numbers" I figured it out :D
* Give every rat a number
* Give every bottle a number; write it in binary
* Give every rat a drop from each bottle for which the bit corresponding to its number is 1
* After the rats have died, find the number where the nth bit is 1 if that rat died, 0 otherwise
* That bottle is poisoned.
Same with me, the word "binary" was a hint.
yep. same.
I just found this channel. I am in love.
Given N bottles, the minimum number of rats would be ceiling(log base 2 of N) I think.
Yup.
The proposed solution would only work for a number bellow 15,000 of wine bottles. Since statistically speaking you could only extract 15,000 drops (0.05 ml) out of a wine bottle (750 ml).
Hi PBS Infinite series, please correct me if I am wrong but if you are administering wine to the rats that correspond to each figure 1 in all the binary numbers 1 to 1111101000 then you will need to administer 4686 (according to my calculations) decimal drops of wine, which seems a very arduous process and I suspect will take much longer than 1 hour. May I suggest you postpone the party, get less fickle friends and use the binary search algorithm I used below, which only needs 1000 drops of wine.
Apologies if this has already been mentioned or is complete bs. Fantastic videos keep it going :)
Forget time, I think with the presented approach you are very likely to make a mistake somewhere. But if replacing friends is an option, then instead of "less fickle" I propose getting friends which are risk takers and doing no tests :P now you have a party game!
A Russian Roulette party, forget the rats lets do the test on the fickle friends. :)
This channel deserves more views. Why aren't other PBS digital series promoting this?
Awesome! Love this new channel! This reminds me of the balance puzzle of determining the outlier out of 27 balls, given three comparative weighing with a balance. What is known is that the outlier is heavier than the other balls.
Hint: The fact that 27 = 3^3 is no coincidence.
It reminds me of a very elegant video of 3blue1brown about the Hanoï Towers and their link to the binary counting system.
Did I see two different haircuts?
Just landed on this channel, I was kind of hoping finding one good of such. My search is over :) Thanks for the whole series!
Man, this was super interesting. Fantastic job making math puzzles fun!
Math puzzles are always fun, even if no rats die in the process. ;)
Amazing new PBS channel! So damn good. I know many people probably wrote it already, but for 100 rats you need at least 7 rats to represent at least 100 bottles in binary, and you need at least 20 rats to represent 10^6 in binary.
neeat and such an everyday problem, thanks for that :D
You're welcome! It's a super fun problem to share with friends. :)
The technique of halving is a similar but simpler approach. Drop feed a rat with bottles 1-500. If it dies, use that set, if not you will be using 501-1000 from now on. This is a diversification of a binary approach that would indicate the precise poisoned bottle by subsequent halving procedures:
Rat 1 halves to 500
Rat 2 to 250
Rat 3 to 125
Rat 4 to 63 (or 62)
Rat 5 to 32 (or 31)
Rat 6 to 16
Rat 7 to 8
Rat 8 to 4
Rat 9 to 2
Rat 10 plays Russian Roulette to spot the poisoned bottle
That takes a lot more than an hour.
You made it too easy by mentioning binary in the intro.
Exactly. When she mentioned binary numbers, she gave it away.
As a software developer who's quite familiar with the binary system though, I wonder if I'd have found the solution had she not mentioned the binary numbers at the start of the video. My guess is it would've taken me a long time, and I might have given up and just continued watching for the solution. ;)
24 seconds into he video and I'm like "yeah, a mathematician WOULD be the one to randomly poison a wine bottle just for math's sake" followed by "of course binary numbers are involved, binary is _everything_[1]"
[1] Source: CS major, can confirm universe is a supercomputer
RATS = ceiling(log_2(BOTTLES))
Amir Alami >=
SuperEuclidean yeah, that's the minimum number of rats required.
Wait, actually shouldn't that be floor(log_2(BOTTLES))+1?
Cajer 1618 floor(x)+1 = ceiling(x)
Amir Alami
floor(3)+1=/=ceiling(3)
Follow up question answer:
You need the next largest power of 2 rats plus one, so 128>100>64, so you need 2^n=128 or log[2](128). Even though you didn’t have a rat to carry the 1024 place in the original example, you also had a 2^0 at the start carrying a zero or one, instead of a “twos place”. So by this logic, you need to have the first POWER of two greater than the given number, and the power will be the answer to how many rats you need. In the case of a million, it’s 20 rats.
7 for 100
20 for 1000000
this one is really simple even "trivial" for those that studied both CS and Math
Enough with this finite stuff, let's talk about infinitely many rats and infinitely many wine bottles. Suppose we had countably infinitely many rats and uncountably infinitely many bottles of wine to test. Using a similar feeding strategy, couldn't I tell you which one of the uncountably many wines is poisoned because the set of all possible binary sequences is uncountably infinite?
Mathoma At that point your chance of drinking the poisoned wine is zero. So it's trivial.
Baby Bop What a buzzkill.
Mathoma this may be overly pedantic, but the set of all binary sequences is not uncountable. the set of all infinite binary sequences is uncountable, but the set of all finite binary sequences is countable (proof by laziness: the first set maps to the reals, the second set maps to the naturals).
+SuperEuclidean
Yes, good point. I had _infinite_ binary sequences in mind, but didn't write that down.
+Baby Bop
But what if you have infinitely many guests, and you don't want any of them to be poisoned?
(Assuming that you can't just mix the wine in the bottles to get the poison per bottle beneath the lethal dose.)
(And assuming that it's possible to distinguish for every rat if it didn't just die from alcohol poisoning.)
Thank you for explaining this in such a good manner. I was always bad at math but always liked the subject. I learned to read binary from a video, damn! gj PBS you did it again.
Regarding the answers - You would need 8 rats to check 100 bottles and 21 rats to check 1 000 000 bottles.
You gave a huge hint when you mentioned binary numbers being the answer. So obviously number all the bottles 1-1000 give each rat a decimal place and for each bottle give it to the rats whose decimal place would be 1 if you converted to bottles number to binary.
But then it would be a binary place, not a decimal place...
Newtonian estimation!
Feed a drop from the first 500 to the first rat, if the rat is poisoned continue with this half,
Then split again and feed 250 to a rat, if it dies continue with this half...
Keep going and you will need exactly 10 rats, 1:500, 2:250, 3:125, 4:62.5, 5:31.25, 6:15.625, 7:7.8125, 8:3.90625, 9:1.953125, 10:0.9765625. This last number is less than one (and would be one if we started at 1024) so we have narrowed it down to one bottle. No need for binary, just keep splitting the bottles in two!
It's a trick question all the bottles are poisoned because technically alcohol is poison. lol. okay I'll leave D:
Dwarrior Yeah but alcohol is something the guests will guzzle down willingly.
Dwarrior u calling us all rats -_-
Since you are testing for a binary state to the bottles (poisoned/not poisoned) I wonder if this could also be applied to anything with n states by using the nth-base number representing each item. Is there any name to this method?
Spoiler at 0:18.......
Yeah, that kinda gave it away for me, too.
for 100 wine bottles we need 7 rats
You'll need 7 rats to check 100 bottles, because 2^6 < 100 < 2^7
And 20 rats to check one millon bottles because 2^19 < 1 000 000 < 2^20
To put it in an other way, you can write 100 in binary with only 7 digits and 1 000 000 with only 20
Here's a different way to think about it: You give the first rat exactly half of all bottles, if it dies, you'll know which half contains the poison. The second rat is fed half of the bottles the first one was fed and half of the ones it wasn't, now by combining the information about the first and second rat, you narrowed it down to a quarter of all bottles. And so on... maybe a little less elegant but that's how I solved it (without using binary numbers directly), although it's essentially the same.
What about N poisoned bottles in M wine bottles?
Magenta Field That's unsolved. For 2 poisoned bottles, the lower and upper bounds for the minimum number of rats needed are 19 and 43 respectively. So, it's possible with 43 rats.
43 rats for how many wine bottles?
Magenta Field I was talking about 1000 wine bottles. But it should hold true for 1024.
If you're interested in these kinds of problems, then read about combinatorics (which deals with questions like these). This problem is also related to information theory and computer science. Here's some links related to this problem:
mathoverflow.net/questions/59939/identifying-poisoned-wines/60312#60312
www.math.uiuc.edu/~z-furedi/PUBS/furedi_frankl_union-free-and-entropy.pdf
math.stackexchange.com/questions/639/logic-problem-identifying-poisoned-wines-out-of-a-sample-minimizing-test-subje
I'm not sure what the solution is for N poisoned bottles and M total bottles, but it is possible to bound the number of rats. With M total bottles and N poisoned bottles, there are M choose N poison bottles. Each rat either lives or dies so it can give you at most 1 bit of information. It takes log_2(M choose N) bits of information to know exactly which N bottles are poisoned. So you must need at least ceil(log_2(M choose N)) rats.
N ≥ M :P
for any number of bottles of wine, you simply need the number of bottles needed to express that number in base 2 which is ceiling(log base 2 of (number of bottles))
I think you spoiled the chalange by saying at 0:19 that answer comes from binary numbers. :/ Please don't do that.
Sorry about that. Y'all are clever! In the future -- less hints. :)
PBS Infinite Series *fewer hints, since less is for uncountable things :-D yeah yeah I was that guy.
Some of us really needed that hint. I think it's valuable to make the problem accessible to a number of people;
Chris Stehlik the hint could have been given with a spoiler warning after the problem was stated
Is it possible to solve this for n > 2 of bottles of wine?
wow she's beautiful and smart.
You could have a table of every bottle divided into sections. with time recording everytime the mouse receives a drop from each bottle in its set. you would then record the time of death for the mouse, and subsequently search for the time related to the drop taken 1 hour prior.
Doesn't work, as there's only 1 hour to find the solution.
They're all poisoned, I've just built up a tolerance to lidocaine.
That's Really cool. It's basically the same method used to work with Hash Tables, which can store and retrieve information on the order of O(1). Really clever.
I have a different solution. Would anyone care to listen?
PT Yamin
Sure, how does it go about it?
After thinking about it, my solution is equivalent to the one in the video, except mine is more visually intuitive. I'm gonna include some pictures:
pichoster.net/images/2016/12/25/PoisonWineSolution.png
Explanation: Each rat drinks from their corresponding bottles. The corresponding bottles are given by the black areas in the picture. Each rat drinks from exactly 500 bottles, so a dead or alive result will tell which half (black or white) of the bottles the poison one is. The reason this works is because with ten rats, each rat narrows down the suspected pool by half so since 1000/(2^10) < 1, you will have exactly 1 bottle left that is suspected of being poison.
PT Yamin
Funnily enough, that is exactly what I first though. It makes quite a bit of intuitive sense as every rat halves the "suspected pool".
Nice graphic by the way.
That's what I came up with, too. It works, and it's not the same as the solution in the video. Our solution gives every rat wine from half the bottles, whereas the solution in the video does not.
lastnameavailable326
Actually the video does, if the amount of bottles were a power of two. The fact that they aren't does however not change the method significantly.
Fantastic puzzle! Googling decoding/encoding gives me information theory. Do you have any recommended textbooks that I can use to study up (say, college/grad-level)? Thank you. ^^
The rest of the rats die of alcohol poisoning
indubitably
Fantastic puzzle! In general, you can test up to 2^n bottles with n rats (including one bottle fed to zero rats).
What I didn't think of was the binary way of seeing it, I saw it as the sum over x from zero to n of n choose x.
The nice thing about this method is that it is flexible if you add some constraints, such as being able to pour at most 5 drops from a bottle (and save more wine from each bottle for your guests), where you can test up to 638 bottles and find the single poisoned one or would need an 11th rat to test all 1000.
Very excited to see what's next on this channel!
I came up with a solution where I could discard as few as 40 to 50 bottles in all cases. It wasn't as clever as the binary solution, but I did have a good time trying to minimize the number of bottles discarded.
0:27 "First, Ima gonna give you [...]" There is such a thing as sounding too casual.
Depends on how you label the bottles, if you start with 0, it's ceil(log2(x)) with x the number of bottles. If you start with 1, it's floor(log2(x)) + 1
Just discovered this channel - looks good. I've been crap at maths my whole life - I only in the last few years grasped what numbers were about. I'm still rubbish, but that stepping stone I just mentioned (I'm sure there is a stepping stones maths problem? :P ) got me hooked. Like with the fibonacci series - it blew my mind with all the patterns of the single digit numbers in the series (repeating every sixty terms.. as well as mirroring etc). I also got my head a bit around conceptualising infinity in different ways as well (realising you can have multiple infinites). A cool thing was just taking y = (1/2)x taken to infinity and mapping it onto half of a hemisphere to get something very close to 3 arcs of a fibonacci curve (when viewed from above)... How I did I don't know, but then I repeated that pattern 60 times onto a sphere using a dodecahedron pattern, and amazingly all these curves seemed to meet at either tangents or right-angles.... but I only constructed this pattern roughly... despite my best efforts (which isn't saying much) I couldn't determine the precise equation to create such a pattern - it didn't seem to be either a fibonacci curve or y = (1/2)x, or an exponential curve either... it was looking like a curve made from an infinite series: having looked into the riemann hypothesis I thought either I'd just got that wrong, or, if it was an infinite series, then there was no way I was going to be able to figure it out... even more annoying was that the pattern of curves meeting at tangents or right-angles seemed to work with hyperspheres as well... I wills nevers knows..... :/
nice riddle, i quite enjoyed this and the hyperspheres video. just one criticism though: mentioning binary in the setup was such a huge hint that solving it wasn't quite as much fun (or trivial...).
Your first solution was my solution as well, and I see there's still six minutes left, but there're actually 11 groups possible with this method. Each rat could sip from 91 bottles, leaving 90 untested. If none of the rats die, then either rats aren't affected by the poison like we thought, or the poison was in the last 90 bottles. Ten more bottles saved!
My answer is different to the one in the video but I'm pretty sure it still works. If you label each rat A to J you can give bottles 1-10 to a single rat each. Bottles 11-55 you can give to two rats; AB, AC, AD, AE, AF, AG, AH, AI, AJ, BC, BD ... IJ (45 combinations). Bottles 56-175 to 3 rats; ABC, ABD ... HIJ (120 combos), 176-385 to ABCD ... GHIJ (210 combos), 386-637 to ABCDE ... FGHIJ (252 combos), 638-847 to ABCDEF ... EFGHIJ (210 combos), 848-967 to ABCDEFG ... DEFGHIJ (120 combos) and 968-1000 there are enough 8 rat combinations to cover the full 1000 bottles. Eg. If rats ABCDEF all die and no others you know that bottle 638 has the poison
Some say TH-cam is "broken". I'd agree. Some of the videos that get extra attention from TH-cam are, first of all, clickbaits and I understand the reasoning behind this. Back to the point: clicking on these videos is a bit of a gamble: one may never know when or if the following video has quality to it or not but if content is satisfactory then the loop goes on... Today TH-cam recommended me yet another clickbait and I fell for it. On the birght side: 10/10 one of the best gambles of my life. Thank you for the brain exercises and interesting thoughts.
Is this related to the Josephus Problem? I just watched a Numberphile episode on it that. It seemed to have a solution in binary that's really similar to this poison rat problem.
But, Array of everything (bottle included) start from 0, not 1.
True, but numbering from 1 lets you save all 100 bottles in case the actual number of poisoned bottles turns out to be zero.
4:38 I don't get it, what does that 1 to 512 means? since you ends just using the rats at 1 or 0. I don't see how this relate to the rest of the problem
100 bottles would be 2^7 so 7 rats, and 1,000,000 bottles would be 2^20 so 20 rats. Awesome series!!!
well combinations work too, nc0+nc1+nc2+.........+ncn= 2 power n and 2 power 10 is 1024, and as for the question you asked answer will be log N base 2 and nearest greater integer is the answer
For 100 bottles, you need 7 rats!!!
- and -
for 1,000,000 bottles, you need 20 rats!!!
To represent (2^n - 1) decimal numbers in binary excluding 0, i need n binary digits. Therefore i will need log_2(n) + 1 binary digits to represent n decimal numbers excluding 0, or log_2(n) counting them from 0 to n-1.
I think some of the comment clips were repeated, or were not from the comments being referenced. You still get a thumbs up though. I'm really enjoying this series, and so is my six-year-old daughter.
For 100 bottles it should only take 7 and for 1,000,000 it should take 20. To figure out how many rats you need, you can take the base 2 log of that number and round it up.
Base 2 log of 100 is about 6.6 so rounded up is 7. 1000 is about 9.9 so rounded up is 10
and 1,000,00 is about 19.9 so 20. Another way to think about it is the amount of rats must be equal to the digits in that number when written in binary.
So we could just mulitply by 2 everytime until we get above that number.
1:2, 2:4, 3:8, 4:16, 5:32, 6:64, 7:128 > 128 is bigger than 100 so we only need 7 binary digits. continue this method and you will find that 1,000 takes 10 and 1,000,000 takes 20.
i already knew binary was useful for computing but wow, that reveal kinda blew my mind
Yea... there's always another solution. If you have 1000 bottles just dump all of them out mixing them together to create a delicious red wine blend and in the process you dilute the poison enough to where it's harmless.
Robert Stolorz what if someone drinks entire thing?
I thought about this as sets.
If you only ha D 2 rats... all you could do is assign bottles 0-500 to the first and 501-1000 to the second.
This means 500 bottles are saved. But adding another rat (for a total of 3) means you can now assign 250-750, decreasing the number of wasted bottles by half.
Supposing the venom is in the 600th bottle, then both the second and third rats would die. Meaning the number is in the range 500 to 750 which is correct.
Each additional rat halves the uncertainty meaning saving more bottles :)
Cheers!
Wait so do you have to pour 1 drop from every single bottle then?
plot twist: alcohol is poisonous anyway. all bottles are technically poisoned
I didn't know binary, my solution was to number the bottle from 1 to 1000; give the first rat a drop from the first bottle of every two (1, 3, ...), the second rat a drop from the first two bottle every four (1, 2, 5, 6,...). To explain this system with four bottles: if the first rat dies you can tell it was bottle 3, since it was the only bottle only the first rat drank from. For the same reason, if the second rat dies you can tell it was bottle 2, if both rat dies it was bottle one, the only one both drank from, and if no rat dies it was bottle 4 since no rat drank from it.
Adding a third rat (which drinks from the first four bottle of every eight) will make you able to test eight bottles, and with ten rats you can get to 1000 (2-4-8-16-32-64-128-256-512-1024). Though I guess it's the same principle.
Nice! Just curious but how long did that take you to come up with. I figured out the binary way but not until i thought about it again 2 nights later
This is my new favorite series. Keep it up!
6 for 100, and 19 for 1 million. This show is awesome. Math is the language of the universe!!!
6:28 -for 100 bottles, minimum number of rats required = 7 , for 1000000 bottles number of rats required=20
How ???
can anyone tell me how to find out the distance between the two corners of the cube diagonally in higher dimensions using pythagorean theorem ,given that length of each side is not a unity..?
You can find the length for the unity cube, which for n dimensions is sqrt(n), then you multiply by the length of one side, since it scales linearly with the cube.
EDIT: Also i found this: www.varsitytutors.com/sat_math-help/how-to-find-the-diagonal-of-a-cube
EDIT2: The general rule for a n-dimensional box with independently long sides is: Square root of the sum of the square of the sides, sqrt(/sum{side} side^2)
Example: A 3- dimensional box with sides 3, 4, 5 would have a diagonal.of sqrt(3^2+4^2+5^2) = sqrt(50)
And if all the sides are the same, like s, it goes like this: sqrt(n * s^2) = sqrt(n) * sqrt(s^2) = sqrt(n) * s
I found all of this out myself but i'm to lazy to make a proof. It's out there somewhere if you want it though.
After the first step, i.e. feeding 100 samples to each rat, and figuring out which group of 100 bottles has the poison, you could feed 11 of the 100 bottles to each rat. If any 1 dies, you know know which group of 11 to look at. If none dies, you know it's the one which you didn't feed to any of them. If 1 dies, you take that group of 11 and feed 2 samples to each of the 3 of the rats, and 1 to each of 5 of the rats. If one of those who took 1 sample dies, you know the bottle. If one of those who drank 2 dies, feed one of the samples it drank to 1 rat, and the other one to the other. Then you know your bottle.
You would need 7 rats if you had 100 bottles of wine and 22 rats if you had 1,000,000 bottles of wine.
With 10 rats we can get 2^10 different outcomes = 1024, which is greater than 1000 and the closest number we can get to it by using only natural numbers.
So if we want R rats for 100 different outcomes we would need to find the smallest natural number R, where 2^R >= 100.
(I'm studying IT so I know from memory that 2^7=128 :P ) If R = 7, then 2^7 = 128 which (as above) is >= 100 and the closest number we can get to it.
So, the mathematical way to find R for any desired amount of outcomes is this: R = ceiling( log_2(Outcomes) ). (Where we choose the value of "Outcomes" and we search for the value of "R".)
:)
I think I figured out the question at the end. For 100 bottles of wine, I think you would need 7 rats. That is because you need a rat for each possible binary position from 0-100.
2^6 is 64, which is too low. 2^7 is 128, which is enough. For example, if you only had 6 rats, you could only encode 64 bottles of wine. But with 7 rats, you can encode all 100 (with 28 to spare!).
Is that the right answer? I figured it out after re-watching the video and noticing 10 rats were needed to encode up to 1000 (aka a 10 string of binary digits). I then did the math to figure out the least exponent of 2^x so that it was >= 100.
People have given the formula in the comments section, but here's it in a form that you can actually plug into your calculator, since most calculators don't have a direct "log 2" button, but they do have a natural log button.
RATS = ceiling(ln(BOTTLES)/ln(2))
Wow, how did you know that?
@@godfreytomlinson2282 Log base-x of y is equal to ln y / ln x. That comes in handy in times like this.
This is just superb! loved it
for 100 you need 7 rats, and for 1 million, you will need 20 rats.
as for 100 the binary is 1100100
and for 1000000 it is 11110100001001000000