In cylindrical batteries, Batteries with more charge bounce very little, while discharged batteries bounce more. This test is performed by dropping batteries on their negative terminal. Therefore, assuming these are the standard cylindrical batteries (aa,aaa,d) drop them on their negative terminals, take the 2 that bounce the least, and this problem is solved in “one test” (by the standards of the problem). 1:45
Realistically, each drop comparison of a pair of batteries is considered "one test", so the fastest solution is two tests with the first pair of batteries bouncing high and being confirmed good in the flashlight. Worst case scenario would be 5 tests (first two tests only contain 3/4 bad batteries, requiring a 4th drop test to determine the 2nd of the four good batteries and then finally the test in the flashlight).
@Tamarocker88 yes you are correct, but by the wording of the video, this would only be technically considered one test, as a test only occurs when batteries are inserted into the flashlight and it is turned on. If you want to constitute a drop of batteries as a test, then depending on how many you drop at once you would be correct. I just said it was technically one test due to the phrasing of the problem
Well, there is the manufacturing date and the guaranteed usage date on every battery nowadays. If it does not have any of these dates, best to get rid of them. 😉
@@charliethunkman I just have a 9V block battery here, lithium cells, and the "BEST BEFORE" date reads "12-2027" No production date, although this I have seen on batteries as well.
I started thinking of the problem before watching the video and went down a similar path where the were 3 possible states bright-dim-off. He did however specify that it was a manufacturing error so its not necessarily the case of the traditional idea of a dead battery. For all we know the electrolyte could have been replaced with bubblegum.
1. I climbed up the mast to change the batteries in my home weather station. 2. I carried four good batteries in my pocket. 3. I took out the bad batteries. 4. I put them in my pocket. 5. ... *bad words*
Interviwer presents the problem: I produce the flashlight from my pocket. ( i always carry one.) And ask what kind of opperation are they running. Why have you allowed bad batteries to contaminate the stock of good batteries? I throw all the batteries out and explain the cost of the time to test these batteries exceeds the cost of four new batteries. I instruct them to buy new batteries out of which i will replace my batteries when they arrive. Go on to explain how ro implement a procedure to avoid such a situation in the future and issue an invoice for a $300 consultation fee.
Right, but you need the flashlight right now to fix something right now, not tomorrow when the stores open, or 30 minutes from now when you get back from 7-11 or some other all night battery selling place. The cost of not fixing it right now vastly exceeds whatever you are going on about.
You're failing to consider the cost of the time it takes to acquire new batteries in your analysis. So long as the testing time is shorter than the time it takes to go to the shop and buy new batteries, introducing the cost of time properly favours testing.
They are from a bad batch and you need to defeat the dark presence, and it's faster to dump out the batteries than pull them out one at a time, and you are sorely lacking time. There, wrote you a half decent plot.
The number of times I've had to deal with customers mixing old light bulbs with new light bulbs.....a very similar sort of problem, except I don't actually know how many (if any!) good bulbs there are. An efficient way to sort them out is very practical. Older two-lamp fluorescent fixtures often require two good bulbs in place to function.
The first example did more tests than was needed with that method. After testing 1 with 2 to 6, and the flashlight didn't turn on, there is no need to test with 7 and 8, as you must have tested 1 with at least one good battery in the other slot, and since the flashlight didn't turn on, 1 must be bad.
Completely true But also remember that the whole point of the first solution was to just get _a_ solution that works. We already knew it was terrible and we were okay with that It's probably a good idea to get in the habit of just letting the bad solution be bad, and not trying to tweak it or optimizing it. That's no point spending time on that when you're going to replace the entire thing with a completely different approach in a minute
(Obviously in this case, that doesn't matter. It's not like this optimization took a lot of time. I did the exact same thing myself when I was looking for an upper bound)
@@daudnobel since you know there are four good batteries, once you've tested it with 2 through 6, you know 1 is bad. While 7 or 8 might be good, if 1 is good, you'll have found another good battery from batteries 2 through 6. As has been pointed out though, this wasn't intended to be an optimal solution.
The first and second strategies are actually the same strategy, just in a different order. When you choose two pairs from the first strategy and test them against each other, that's the same as the group of 4 in the second strategy.
The order in the first strategy is about 20% more efficient (in terms of "average"/expected number of tests) than the order in the second strategy, though. In fact, the first strategy is more efficient than the 7-test method as presented in the video.
@@yurenchu its a battery u test 1 on lips if its charged u keep it, if its dead u toss it. u check next battery on lips if its charged, flashlight has 2 battery's if neither was charged ur 2 bad battery's down 4 good 2 bad to go, continue testing at worst it will take 5 tests to know the rest are good/bad/ identify the 2 groups of battery you can also bounce them, charged batterys have more bounce. alternatively you could use a multimeter or many batterys today have a charge bar on side of them for ppl that dont know how to test them with there tounge NO electrician ever sat there with a pile of batterys putting them in at random to find out which ones where charged. theirs a number of ways of detecting charge level they would use one of them before they resorted to testing with a flashlight in groups of 2, they would at least use a flashlight that held 1 at a time reducing the number of tests to 5 from 11 if you do it with 2 and ur loading 1/2 as many each time also/half the time per test
@@violetquinnlaw The original commenter and I were talking about the methods that were presented in the video, not about what kinds of stunt experiments Johnny Knoxville (or Adam Savage) would do with a bunch of batteries. Furthermore, the question in this video is meant as a logic puzzle, not as a test for the recruitment/hiring of electricians. The principles in this logic puzzle can be used in/extended to all kinds of (data) filtering and (abstract) sorting problems, the "flashlight" and "batteries" are just the dressing up of the problem to make the conditions of the problem more accessible to the general viewership of this math/puzzle channel. Likewise, the so-called "Secretary Problem" is not really about hiring secretaries, and the famous "Monty Hall Problem" does not really apply to any real game show.
I would Split them in two groups of four, test all the combinations in one group, if none of those work It means there's a maximum of one good battery in that group. Then start testing the second group, It would take at most two tests to single out the faulty battery in the second group. So at most It would take 8 tests in total, in the worth case scenario.
Real story: My parents were setting up a 3-way switching. They tested it and it didn't work out. So they searched the error, didn't find any, tested and tested and searched and searched. They tried replacing the bulb, they even tried replacing the light base. In the end, it turned out, they used two bad bulbs AND two bad light bases and the 3-way switching was set up correctly from the start.
In the first example the maximum number of tests should be 15 i think. After 5 tests you will know if your first battery is good or not. You will have to have hit at least one good battery at that point and if the flashlight never turned on then your first battery is clearly dead. There is no need to continue testing that battery.
oh snap, was wondering what you're talking about and suddenly, yep, that makes sense. In worst case scenario the last 4 batteries will be good, not need to test against all 4. nice catch
@@jerkison Agreed. TBH, I meant 100 with an exclamation mark, but I left it as is to make it also look like a factorial. Even 100 is not a particularly good upper bound.
I chose the splitting into two groups of four method first because I was a computer service engineer and if you are trying to find a faulty component in a group you can speed up the process by using the 'half split' technique. I quickly found 8 as the minimum.
The optimal construct can be summarized using elementary school Olympiad technics: pigeonhole principal. We have 4 good batteries split into 3 groups of size 3, 3, 2, then at least one group has a pair of good batteries. Then we check *every* pairs inside each group, that's total 7 pairs to check.
I remember the pigeonhole principle being taught to me by a programming teacher (in the context of data structures, iirc), and while I was trying to think of why the optimal solution worked the way it did, that's what I remembered. Interesting to see the exact same term come up in a different context.
Why not 8?? I thought this gonna be C(8,2)*C(7,2) or something? Kinda dislike pigeonhole problem because we need to model the problem first, and that is so difficult
@@arolimarcellinus8541 By splitting the batteries into distinct groups of 3, 3, and 2, the first two groups only have C(3,2) combinations per group to check. Worst case scenario, after six tests none of them light, indicating that each group has 2 dead batteries 1 good, thus by definition the group of 2 must be good.
It's basically a variant of the classic "Find the counterfeit coin using only a balance scale" puzzle, except here there are four counterfeit coins and you can only weigh two coins at a time. Surprisingly, even given these differences, the solution turns out to be remarkably similar.
It's thanks to my familiarity with this puzzle that I had the idea of splitting up the batteries into two groups of 4, then intuitively decided 2 groups of 3 and a pair was much more manageable probability-wise. I forgot how to solve the coin puzzle though so I was flying blind but it turns out I was on the right track 😅
Another solution is dividing the group in 3+5. If the pairs of the 1st group (3) are off that means worst case there is one good and others bad and the group of 5 has 2 bad and 3 good batteries (total 3 tries). Then take the 2nd group and do 2 pairs (4+5 and 6+7), both are off means both the subgroups have one good and one bad battery and the 8th one is good (total 5 tries). Now take the 8 and pair with 4 and 5 (total 7 tries).
This is definitely inventive, and also completely correct, so I'm impressed. But I wonder if you've noticed that it's fundamentally the same as the solution in the video? It's just in a different order If you look closely, you'll see that you test {6,7} as a pair, and then you never test either of those batteries with anything else. So your group of five is actually a group of two{6,7} and a separate group of three {4,5,8} You also test all three possible combinations of {4,5,8} ( You test {4,5}, {4,8}, and {5-8}). So you're doing a trio, another trio, and a pair, just like in the video
@@douglaswolfen7820 Exactly. I was going for the 3 and 5, and after the 6th test I decided I needed to test 4-5, 5-6 and 4-6 in stead of 6-7 to get the second 2/3 bad ones. So the groups became 1-3, 4-6 and 7+8.
Looking at probability in this problem isn’t very interesting because there’s always a chance that the first pair you try will be right. Deducing that the minimum number of tests needed with perfect luck is one isn’t very hard.
Not sure if this is optimal but my solution would be: Group the batteries into 4 pairs and try every pair. 1 & 2, 3 & 4, etc. (4 tests) Either: one of the pairs will have 2 good batteries (and work, thus you are done); or, all 4 pairs have exactly 1 good and 1 bad battery. (If any pair has 2 _bad_ batteries, it necessarily requires there to be at least one pair that had two _good_ batteries, so if none of the pairs just worked, then we have already ruled this out.) So in the worst case scenario, we've conducted 4 tests and we now know that each pair of batteries that we tested must have 1 good and 1 bad battery. Take any two pairs; call a pair "AB". Test 1 battery from each pair; there are 4 possible permutations: AA, AB, BA, BB. As we know that each pair has 1 good battery, exactly 1 of these permutations will match up the two good batteries. It should take no more than 8 attempts to get 2 batteries that work.
correct me if i'm wrong: shouldn't take more than 6 attempts, really . after trying out the first 4 combinations, pick any two pairs (each pair should have a bad and a good battery) and do two more tests with one battery from each pair. One of them must have 2 good batteries
@@thejaskodoth4630 Two pairs that each contain 1 good & 1 bad battery have 4 possible arrangements, and only 1 of them puts the 2 good batteries together. If you test one battery from each pair and it _doesn't_ work, then there's a 1/3 chance that you happened to pick the 2 bad batteries - in which case using the _other_ 2 batteries will be the good combination. But the other 2/3 chance is that one battery was good and one was bad, and you don't know which is which, so you may have to exhaust all 4 combinations to find the good pair.
Take the two pairs with one good amd one bad battery.. let them be a0,a1 and b0,b1.. test a0 with b0 nd b1. If we a0 was a good battery we would have got a good pair.. (
Elegant solution, I didnt find the 7 tries one, only 8 tries solution. But, what if the challenge is to find two working batteries as fast as possible, is it still better? My hunch without pen and paper is that the 8 solution requires fewer tries on average than the 7 one?
@@ShankarUtthandyV it only takes 6 tries because by powers of deduction, if none of your 6 tests lit up, then the remaining untested pair must be good, no test needed.
I GOT THE 7-TEST SOLUTION! my initial solution was 10 tests, but i misunderstood the question for longer than i’d like to admit (thought we were trying to sort the batteries) once i understood the question i came up with the 7-test solution while you were explaining solution 2.
Haven't watched the video yet, but I think you can do it in 6 tests: -Divide the batteries into 4 pairs, and test each pair. If no pair works, that means each pair was a good/bad pair. -Take two good/bad pairs, and you know there are 2 good batteries within that. Test each battery with its corresponding partner in the other pair. -Realize that there are still some untested pairings, and it's probably going to take a total of 7 tests. _edit:_ _Ok, it looks like this actually takes 8 tests_
I came to this conclusion as well before watching the video, and I believe you can still count this as 7 tests, because if you complete the 7th test without finding a pair of good batteries, you don’t actually have to perform the 8th test since it’s guaranteed that the remaining pair are good batteries.
I attacked it in the same way, and think 6 is the minimum. Check my work! You don't need to do an additional 7th test if none of them light up, because using deductive logic, the remaining pair after 6 rounds of tests must be 2 good batteries. Please check my logic I think I did it in 6 on my first try, and with multiple pathways! Test 1: 1+2 Test 2: 3+4 Test 3: 5+6 Test 4: 7+8 If any of them lit up, you found your good pair in the first 1-4 tests by pure luck. If none lit up, then each pair should have one good, one bad. Test 5: 1+3 = good + good, or bad + bad, or bad + good. If light, you won by #5. Test 6: 1+4 or 2+3 = if either test lights, you win, if they stay dim, you know the remaining pair is 2 good batteries, and you still win.
@@petertrzos6645 Ah, this a good thought process, the logic being that you use the first 4 tests as a way to obtain 4 good+bad pairs, and then you only need to use 2 good+bad pairs to determine the 2 good batteries within them. However, I disagree that this requires only 2 additional tests for a total of 6 tests. To be explicit with the possibilities, there are 3 cases when taking (1, 2) and (3, 4) as the 2 good+bad pairs and finding that (1, 3) fails the 5th test: Case 1: 1 is good, 3 is bad. Then (1, 4) cannot fail the 6th test because we know 2 must be bad from the 1st test, leaving 4 as the remaining good battery. Case 2: 1 is bad, 3 is good. Then (1, 4) will fail the 6th test, leaving (2, 3) as the pair of good batteries. Case 3: 1 is bad, 3 is bad. Then (1, 4) will fail the 6th test, leaving (2, 4) as the pair of good batteries. By doing the exact same procedure with (1, 3) as the 5th test and (1, 4) as the 6th test, the “remaining pair” you mention is ambiguous, since we encounter 2 possible outcomes when the 6th test fails: (2, 3) as the good pair in case 2, or (2, 4) as the good pair in case 3. I do agree that you have a singular“remaining battery” that need not be tested (battery #2), but we still end up needing to find which battery in (3, 4) to pair it with; to differentiate them, we will require one final, 7th test. Ultimately, what you already state for your 6th test (“1+4 or 2+3”) will need to split into 2 tests. Let me know what you think!
@@petertrzos6645 If 1+3 is dark, and then 2+3 is also dark, you do know that 4 _must_ be good (and 3 was bad), but you still don't know whether 1 or 2 was the good one. The 1+4 and 2+4 tests are still required. You can argue that after the 7th test, you "know" now, but you still _technically_ haven't lit the flashlight yet. I don't know if that means you have to count the last pairing. 8 "battery insertions" before the light turns on, worst-case scenario. So depending on the definition of success, 7 or 8 tests.
Even if the bounce test was anything more than urban legend (and scientific testing has demonstrated that that’s all it is), that test wouldn’t necessarily apply to mismanufactured batteries, only to drained vs charged batteries. But I did like the humor of your comment. 😅
My explanation of 7 being the minimum is that in Testing 2 at a time, the most we can hope is to eliminate one possibility per test. We have 8 batteries so best case is 7 eliminated needing 7 tests.
@@verkuilbthat’s not true. It has been repeatedly shown that dead batteries do bounce higher. It may not accurately tell you if it is dead or just has a low charge, but a used battery will bounce higher than a new one.
Really fun puzzle! As an additional note, I think you can also show that 6 tests is never enough with simple brute-force coding: 1. Generate all possible combinations of good and bad batteries. There are a total of 70 such combinations (8 choose 4). 2. Generate all possible combinations of 6 tests. There are a total of 376 740 such combinations: 28 possible tests (8 choose 2), which gives "28 choose 6" = 376 740. 3. Then execute each 6-test combination for each combination of good and bad batteries. 4. As the end result, you should see that for all 6-test combination, there will be at least one combination of good and bad batteries where all tests leave the flashlight unlit. 5. This is a total of 26 371 800 (376 740 * 70), which should be easily doable for a computer. Quite an ugly way of doing it, but still a valid proof. (But I still prefer a nicer proof via graphs).
I solved the problem on my own and I got 6 tests including the final one: First, I compare them pairwise. b1 + b2 = false b3 + b4 = false b5 + b6 = false b7 + b8 = false Where I note that b is the battery and the number on the right is its index Given the worst-case result, we will find no working result, this is possible with one of two combinations: 1 - t | f 2 - f | t 3 - t | f 4 - f | t 5 - t | f 6 - f | t 7 - t | f 8 - f | t That is, t - true and f - false will always alternate through 1 Next I start checking through the 1 index b1 + b3 = false b2 + b4 = true Given that we have a failed layout where b1 + b3 will not be true, we get that together with the successful test b2 +b4 we have used 4+2 = 6 tests
@@nixhalla3uk27 In case you did not watch the full video and explanations, your solution does not actually account for worst case as you missed 2. If b1 is false, b2 is true, b3 is true and b4 is false, then b1+b2 and b3+b4 would be false. Then, b1+b3 (false + true) and b2+b4 (true + false) would also both be false. Next, b1+b4 (false + false) would be the final false pair before b2 + b3 (true + true) would get tested.
@bok4822 see my example in the comments. The answer is "6 tests". Logic allows imputed tests that the graphing solution cannot detect. One battery does not get tested and does not need to be tested.
and yet if u used a single battery flashlight or tested it on your tounge by bouncing it or with a multimeter it would be 5 tests of a single batterys not 2 MAXIMUM :P
Cool problem! I first jumped to the 4 groups of 2 approach, then after those fail in the worst case, working with just two of those groups. Once I saw the optimal solution, I immediately saw it in terms of combinations. the 8 step approaches being 4 * (2 choose 2) + (4 choose 2) - 2 and (4 choose 2) + 2 * (2 choose 2). The optimal solution being 2 * (3 choose 2) + (2 choose 2) cleverly removes one step, but I feel like it's easy to skip it in consideration due to dividing them into varying group sizes.
@@mr.cauliflower3536 So now you have to figure out how much tingle does a good battery give, and how much tingle for a bad battery. Maybe this will be the next test question.
@@ralfbauerfeind8236 No, I've been using the 'taste' test for penlight batteries for over 35 years now ever since I was a teen. Empty batteries don't taste. Batteries with charge tast sour. You just press the back (- pole) to the inside of your upper lip and put your tongue on the tip (+ pole)
My gut led me to 8 tests Presh presented as solution 2. I don't think I would've gotten the 7 test solution if thought about it longer. Interesting problem.
@@3057luis I definitely felt okay about defaulting to the 2nd 8 test solution, but looking back I kick myself a little bit for not having the mind to find the 7 test, most correct answer. The two corollaries I derived from the rules that led me to the 2nd 8 test were: a) a negative test only proves 1 of the 2 tested is bad therefore b) "grouping" batteries and exhausting the tests within that group will prove that all but 1 within the group are bad The first corollary I stated is fairly obvious. The second less so, but still not that difficult. Where I failed is not putting much thought into finding the optimal groupings. I approached it as simply as I could -- "we start with an even number, so let's split in half" >>4+4 "still even numbers, so let's split in half again" >>2+2+2+2 "revert back and crunch the numbers" >>4+4>>6+2 tests. I don't think I would've thought to think outside the box with uneven groupings with 3+3+2, even though it was the only other sensible groupings to evaluate. Oddly, thinking about how I think, I do think I would've gotten to an optimal solution if the starting number of batteries was different. Say 10 for example where 5 are bad, or an odd number of batteries where roundup or rounddown(n/2) are bad. I think my thought process seemed to get stuck in the comfort of 8 total being a power of 2, so I didn't consider groupings that weren't also powers of 2.
Same here, I thought of forming 4 pairs to test right away, calculated that it needs a max of 8 tests, this seemed good enough so I pressed play. If somebody told me "7-test solutions exist, if you find one yourself you win $1 million" I'd probably find one eventually, but if I'm given this as an interview question I'm happily stopping at 8.
only 6 tests needed , and it's a very simple task . I'm happy i solved it straight away in my mind. Obviously 2 groups of 3 items each and 2 items aside ( and there no need at all to test this 2 batteries ). In case if both batteries are good in the group of 2 , the other 2 good batteries may be placed only in 2 ways : 1) both are in one group of 3 and you will pick them up while doing tests in this group , or 2) each battery in each group of 3 , in this case there will be no working torch in all 6 tests. So you will come to the conclusion that the 2 batteries which were put aside in group of 2 are the good ones without any extra test. In all other cases if you put aside (in the group of 2) only 1 good battery or no good batteries at all, you 'll pick up the working pair during your 6 tests in the 2 groups of 3 batteries each Reply
It takes 7 tests because the prompt says to include a verification test. Even though this method will assure tha the group of two are both good once you exhaust tests in both groups of three, you still have to "test" the group of two to verify.
14:20 The proof has a gap that I'm sure is fillable, but should be filled: It assumes there is a group of 3 completely disconnected, the group that he "WLOG" chooses 1,2,3. Instead, he should say that this group should exist because: there 8 choose 3=56 groups of three nodes. Each edge can add to 6 groups, when you associate it with the other 6 nodes. So with 6 edges, one can add 6*6=36. However, then one group of 3 must sum less than 1, so that's the disconnected group. In fact, this argument would work with 9 edges, still there has to be a group of 3 disconnected, since 9*6=54
@@andyp5899 yeah - the first solution was waay too simply explained and when he went to "graph theory" i was hoping we'd get a simple explanation too but then it was all verbal and no pictures - very bad made the video less effective for me
Thank you! That assumption was driving me nuts. Something just felt off in the proof by contradiction and it took me a few minutes of restating the proof more formally in my head, to put a finger on it. Then I scrolled down, and sure enough, someone had pointed it out in the comments.
@@physicssquirrel Yeah, I spotted the hole while I was waiting for him to explain the rest of the proof once he'd pointed out that 4 had to have an edge to 123 and I'd had my "aha!" moment. I did come up with an alternate patch for the hole: Definition: an "induced subgraph" is the graph you get by taking a subset of the nodes from a graph, along with all the edges of that parent graph that directly connect pairs of nodes in that subset. There must be at least one edgeless induced subgraph with 1 node since the unique graph with 1 node has no edges. There must be at least one edgeless induced subgraph with 2 nodes since when you take any node, there are 7 other nodes, so 7 potential edges to the first node, but you only have 6 edges available. There must be at least one edgeless induced subgraph with 3 nodes since, taking any edgeless pair of nodes, each of the other 6 nodes has to be connected to at least one of those 2 by an edge to avoid forming an edgeless 3 node induced subgraph, but then there are no edges left to connect any of those 6 nodes to each other. This approach requires more thought for induced subgraphs with more than half the parent graph's nodes since you can't just look for subgraphs among "the rest" of the nodes - after taking an edgeless group of 4 nodes, you have 4 nodes left, so forming a group of 5 that must be edgeless has to include at least one of the first 4...
I think I found the seven solution. Putting it in comments before I see the solutions: 12,13,23,78,76,86,45 I initially found a solution that required 10. I decided to try again once I heard the actual optimal numbers. It’s funny how much easier it becomes once you have a goal number.
Seeing the proof at the ending was interesting, because that’s exactly how I figured it out. I drew out the 8 batteries, and looked for a way I could connect them with 7 lines, with no groups of 4 not connected.
I've never been in an interview where a question like this was asked, but it seems like the amount of time that would be given to answer wouldn't be sufficient to figure out the best answer. So, it just becomes a game of, "Did you Google common interview questions and memorize the answers before hand?"
You don't need to solve it, they just want to hear you try to work it out. It's an interview, not a test. They know you could just Google it, and they already know the answer. The question is if you have a problem in the future while working for them, and the answer isn't known, are you the sort of person that gives up when you find the first solution no matter how bad it is? Do you get frustrated? Or on the other hand, do you hold on trying and trying refusing to give up until you've found the ideal solution at the cost of wasting a ton of time better spent doing something else? There's a ton someone could learn from watching you try to solve this. Probably if you answer 23, you aren't getting the job. If you answer 15, then it depends on how you thought about it and how you responded. If you get 8 in a reasonable time, they are going to be impressed. If you get 7, they will assume you memorized the answer 😉
It took me maybe 5 minutes to come up with a way to do it in no more than 8 steps. The key is to understand that if you pair up the 8 batteries into 4 pairs, there are only two possibilities: either at least one pair will contain two good batteries, or every pair contains 1 good and 1 bad battery. If every pair contains 1 good and 1 bad battery, then just take any two pairs and try all 4 possible ways to take 1 battery from each pair to find two good batteries.
Nice problem and nice explanation of various solutions. I am glad that the first solution came to my mind required 7 tests. But the solution is a bit different than the one that you mentioned. Here is my solution, test pair of batteries like 1-2, 3-4, 5-6, 7-8. Assuming non of these passed, now we know that each pair has a bad battery. Take first two pairs and test 1-3. If it fails then we know that battery 2 and 3 both are good or both are bad because both failed with battery 1. Now we test 2-3 and assuming that both are bad, the test fails. Now test 1 and 3, the test should pass. So in total we did 7 tests (including the passing one).
Agreed, this is only something a mathematician would care about. A multimeter is a tool we all have. This test to ferret out candidates will give you a student, not an employee with experience.
Around the 14:30 mark, there seems to be a jump in reasoning. It's stated that there is a group with at most 3 nodes with no edges between them. We then continue for the proof by assuming that there is a group with exactly 3 nodes with no edges between them. Note that this can easily be remedied but in the video this step seems a bit off.
In the basic approach 2:30 I am surprised that you tested the first battery with all the others. You can just test it with other 5 ones and that is sufficient. Any 5 batteries include at least a good one, you don't need all of them to guarantee the existence of a good one.
Absolutely! And while we’re at it… What happens if you pull the wires out of the flashlight, and require so that in your test, the batteries are in parallel instead of in series? And what about if you line up three batteries in series-will the flashlight work with only two good batteries, or do you need three in that case?
Great explanation, but I think there’s a flaw in the proof by contradiction for the 6 comparisons. It doesn’t fully cover cases where only 1 or 2 nodes are unconnected, which could affect the outcome. To be thorough, it would need to address these scenarios to confirm 6 comparisons aren’t enough. Still, an interesting puzzle!
In the pairs test you only need 7 tests, not 8. Consider 12, 34, 56 and 78 all tested "off". Then you test 23, 45. Suppose they tested "off". Then the next test will be "on". Total 7 tests. edit: correct solution is 7 tests, but you test 23 and if it fails test 24. It will work. Thanks erendorn.
I don't think this is right. What would the next test be after 23, 45? Maybe we could say 67 should be the next test, but 67 could still fail if the functioning batteries were 1, 4, 6, and 8. Maybe we could say 18 should be the next test, but 18 could still fail if the functioning batteries were 1, 3, 5, and 7. Maybe we could say 25 (the only untested pair of 2, 3, 4, and 5), but 25 could still fail if the functioning batteries were 1, 3, 6, 8.
You can test 13, 14, if still off then 2 is good. Test 23, if still off then 4 is good. You picked the wrong tests, but you are still correct that only 7 tests are needed with pairs.
@@NesrocksGamingVideos no, worst case is 7. You need at worst 4 tests with the 4 pairs, as per your initial post. If they all tested off, then you know that one of 12 is good, and one of 34 is good. So you test 13 and 14, if both fail, you know that 1 is bad, and so 2 is good. Then you test 23. If it works, then 23 is good, if it doesn't, 24 has to be good. You don't have to do a 4th test.
If you phrase the question as "how many tests do you have to perform to know which two batteries are good?" then the answer is 6 because you don't have to perform the last test to know that the last two are good batteries.
It doesn't make a difference if you rephrase, you didn't need the last test anyway, because of the task's conditions that say there are only 4 bad batteries, so the last one always has to succeed. It would only make sense as a demonstration that the method works, but that's not how you solve math problems...
@@Fossil_Frank Or to put it another way: The puzzle works equally well if we don't count the final "test", but all that would do is reduce the number of tests for any method by one, which is a meaningless difference. Furthermore, if the goal is to make the flashlight WORK we still must insert two good batteries. Merely knowing that there ARE two good batteries is insufficient. Or to put it one more way: Only a mathematician would be happy with a 6 test solution, and will then sit in the dark feeling smug.
@@Lord_zeel First of it's not the goal, the task asks how many tests are needed and therefore, the provided anwser is wrong. Second, it does make a difference. Imagine you add a needless coloring to the Four Color Algorithm. Suddenly, you can't go below 5 colors in any planar graph, which would at best make your applications of it crap, or if everyone adapts it : there would be unpleasant implications on a lot of technology you use daily. Furthermore, this argument refers to practicality, but let's be honest here: would you really devise a method for minimizing tests here, instead of just testing at random until you find a working pair? It'll certainly be faster than coming up with a clever solution and it's not like anyone tests batteries like that. So no, that kind of mindset doesn't make sense. It doesn't seem like you have a science background, so you may not be aware, but these kinds of problems form classes that when generalized, provide valuable insight into things you'd never think related. Also, while this is a (deliberately) trivialized scenario, so that it refers to concepts everyone is familiar with, most real solutions can't be easily empirically verified in general, many can't at all. For example, how do you check empirically if the before mentioned Four Color Theorem really holds? By testing it on all planar graphs? There's an ininite amount of them. This is the whole reason people stress about mathemathical rigour and minimalistic solutions, while also not caring at all about steps to "show" that they work - you're supposed to be convinced of that by analyzing the method itself and it's proof. If that's not enough then you either don't understand it, or there's actually something wrong with it.
@@Lord_zeelA mathematician, or a supply chain person in a lit room, who can ship the batteries without a qualm to whoever needs them, or someone doing maintenance checks, etc. There are plenty of people interested in something being ready for later use that are fine not using what they’re testing
He did specify that the final insertion counts as a test. This does not fundamentally alter the difficulty of the problem, it just adds one to the optimal count.
"There is a smarter testing procedure that will get an answer in only 8 tests" Me: Yes! "And this is only 1 short of the optimal number of 7" Me: Dammit!
Same. Once I knew there was an optimal of 7 tests, I could find it, but my first idea was the 4 pairs solution with 8 tests. In its defence, you have a less than 10% chance of actually needing to do all 8 tests.
@@tealkerberus748 I'm pretty sure that on average, you'll find the good batteries faster with the 4 pairs solution, because when you try a pair and it doesn't work, the odds of getting a good pair if you throw both batteries in the "bad" pair away are always higher than if you keep one of the "bad pair" batteries, since you know you're trading a MAXIMUM of 50% good batteries away for a MINIMUM of 50% good batteries (the remaining batteries are either 3 good 3 bad, or 4 good 2 bad).
I expected it was respectable, but not maximal. NOW... Which is most often quickest ("efficient"?)? 3-3-2, but I'm intrigued about comparing 12, 45, then 78, then 23, 31, 56 and 64. Probabilities... grrr... lunch trumps. Anyone? ;)
It is 4, as there are 4 possible size-2 subsets of set {1,2,3,4}, excluding {1,2} and {3,4} as they have already been tested: {1,3}, {1,4}, {2,3}, and {2,4} 2 tests cannot narrow down which of these will guarantee a success.
This is the best solution and heres why If there are 4 good batteries, you split them into 3 groups This means 1 of the groups will always have two batteries If there are 10 good batteries, you group them into 9 groups (20 batteries total). Thay means one of the groups must have 2 good batteries. The groups would be 3,3,2,2,2,2,2,2,2 A group of 3 batteries has 3 different matches to make and a group of 2 batteries has 1 match (lets call match "m") 3m+3m+1m+1m+1m+1m+1m+1m+1m 13 would be max amount to find 2 good batteries in 10 good and 10 bad batteries
I wrote a script to check which method is fastest on average (out of the 3 good ones), these are the results: Method 1 - 1 - 15 2 - 14 3 - 13 4 - 12 5 - 4 6 - 4 7 - 4 8 - 4 Method 2 - 1 - 15 2 - 10 3 - 6 4 - 10 5 - 6 6 - 6 7 - 9 8 - 8 Method 3 - 1 - 15 2 - 10 3 - 10 4 - 12 5 - 7 6 - 7 7 - 9 Notation: How many tries are required in how many cases, so 2 -14 means there are 14 configurations that require two tries to solve. And this is how many tries each method needs on average: Method 1 AVG - 3.34 Method 2 AVG - 4.08 Method 3 AVG - 3.61
In the final method you should be careful with the order of tests, for the best average speed you should try one pair of the first group of three, then one pair of the second group of three then the last group/pair, then another pair of the first group then another pair of the second group then the remaining two tests; that's one of the good orderings of the tests. Considering your notation, in order to not confuse the reader, you may replace the first hyphen in each line by a colon. E.G Method 1 : 1-15 2-14 ...
With good ordering of the tests, I found that the third method gives: 1-15 2-14 3-13 4-8 5-7 6-7 7-6 And that makes an average of 3.32857 which outperforms the first method. Please check it to confirm.
@@ahmedouerfelli4709 you are correct. Doing the tests in the order you described does result in better average takes, 3.32 as you said. Which is just a hair better than method one. Nice catch
Nice work! However, I think there is a mistake in the list of "number of configurations" for Method 2 ; it should be [15 , 10 , 10 , 6 , 6 , 6 , 9 , 8] instead of [15 , 10 , 6 , 10 , 6 , 6 , 9 , 8] That would lead to an "average" (or expected number of tests) of 4.02857... tests, instead of 4.08 tests. By the way: the expected number of tests for the 23-tests approach in the video, is... exactly 7 tests!
@@ahmedouerfelli4709 Actually, an even more efficient order for the 7-test method is to start with a pair from each group during the first three tests, then to do the two other tests from one group of three, and end with the two other tests from the other group of three. Or concretely: (1&2 , 4&5 , 7&8 , 1&3 , 2&3 , 4&6 , 5&6) This gives the relative frequencies of success per test as [15, 14, 13, 8, 8, 6, 6] and hence the average/expected number of tests is 232/70 = 3.31428571... EDIT: I have just verified that this order is indeed the _most efficient_ order of the seven pairs in the 7-test method, and that the order as presented in the video is the _least efficient_ order of the pairs in the 7-test method (253/70 = 3.61428571... tests). (If we divide the eight batteries into three groups A, B, and C, with A and B each containing three batteries and group C containing two batteries, then this most efficient order can be represented as ABCAABB ; and the least effiicient order as AAABBBC . There are a total of 70 orders (each with 72 equivalent permutations), but they can be reduced to 21 distinct cases (since for example AABBCAB works out the same as AABBCBA ; or AABACBB works out the same as AACABBB.) If the seven pairs of the 7-test method are just put in random order, then the expected number of tests is 240/70 = 3.4285714... (which is also the expected number of tests for the order AABCABB ).
Maybe it’s the security person in me, but my first impulse is always to hack the problem instead of doing the math. I appreciate the math, but precision of language is an equal challenge, and is relevant to every word-based problem.
Practical real-world solution: You can do it in six tests if you test one at a time. With a bit of wire, you can overcome the flashlight’s design limitation of requiring two batteries, and unless it was a uselessly dim flashlight to start, the bulb should still be visibly alight with half the voltage. Worst case scenario there you hit a good battery and then four bad batteries after which you know which batteries are good and your sixth test lights the flashlight fully.
My method required 17 tests. You're good. If anyone is curious, a group of 5 batteries is guaranteed to have at least 1 working battery. Isolate 5 batteries, that leaves 3. Test each of the 5 against the remaining 3. This will take 5×3, or 15 tests. If all 3 fail, the remaining 5 contain only one bad battery. Test any 2 pairs without repeating a battery and success is guaranteed.
My flashlight is actually a Power Bank, that has 2 of 18650 3V batteries. They are connected parallel - yes, they are, not series. Putting two different condition batteries ruins the good one and burns the house. But testing would be easy, one at a time so 2 goodies are found in 4 tests only plus that only-for-this-game rule that you must put the light on in the end even when you know already which are good.
What if you arrange them in sets of 2 (so you have 4 sets of 2). Then you try the first set, if it doesn't work you try the second set. If the second set doesn't work, you change one battery from set 1, with one battery from set 2, and then try set1 and set2 again. Worst case, these 4 tries don't work. Then you move on to set 3 and set 4 and do the same. This should theoretically only take you 6 tries to get to the correct answer. In the first group (first 2 sets) each set can either have this (W = working, B = broken): WW WB BW BB If either set has a WW, then you win in 2 tries, if both sets has a WB or a BW, then you win in 4 tries. The only situation you don't win in 4 tries, is if the group has WB BB, in which case, it means that the second group (the set 3 and set 4) necessarily has a WW, which can be the second one you try. So theoretically it should take at most 6 tries to get to a correct pair. Is there an error here?
The error is: Considering the case where each pair contains exactly 1 good battery, in tests 3 and 4 after the swap of two batteries between the first two pairs [WLOG let's say 1 and 3], if they are both good or both bad, it will make no difference.
@@snowthemegaabsol6819 Yes exactly :D So to fix this, we just do another switch (since we keep track of the batteries) and have 2 more tries, which puts the maximum number of attempts at 8.
my answer was 15 tests, by using the first solution but eliminating redundant tests: 12, 13, 14, 15, 16 (after these tests, it is certain that 1 must be bad) 23, 24, 25, 26 (after these tests, it is certain that 2 must be bad) 34, 35, 36 (after these tests, it is certain that 3 must be bad) 45, 46 (after these tests, it is certain that 4 must be bad, and the other 4 batteries must therefore be good, so one more test is needed)
@@skitzocalypso5840 you never get to them because with the assumption that the tests go as badly as possible you cut out the batteries from 1-4 as 100% bad and 5-8 are good. The logic for elimination is as follows: I am holding a battery (1) if this battery is good then there are only 4 bad batteries in the pile. If I test it against 5 batteries, I MUST find at least 1 good battery within that 5. If the torch doesn't light even though I'm certain a good battery HAD TO take the second slot next to (1) then I know (1) is bad. Thus you identified a bad battery - now the remaining pile only contains up to 3 bad batteries. You never need to test 7 and 8 because the objective is to find TWO working batteries so you stop after that happens. 7 and 8 do contribute but only by their properties as being part of this group which must contain 4 bad and 4 good batteries.
@@skitzocalypso5840 if a pair from 1-4 is good then you ended the testing early by finding it. you simulate the "worst case scenario" because lucking in and hitting the good ones on the very first try is always a statistical possibility, but has no bearing on what our strategy should be.
it's a process that would end at any point if you have hit 2 good ones, and our goal is to find a solution where no matter how "unlucky" we are with the process, we find the "goal" eventually. And then to refine the solution to find the "goal" faster.
I think a part is missing in the last demonstration, it took me a very long time to understand what they trying to do with the "4 nodes without links between them".
@@ShawnF6FHellcat The first thing is that you stop once you get the light. So there is no decisions to make depending on the result of a test. You can represent the batteries with nodes, and the tests with edges. You have 4 good batteries, i.e. 4 good nodes. To "win", you need to have an edge between 2 of theses 4 nodes. i.e. to have a test with 2 good batteries. The second thing, is that we assume the worst case. From a given graph with 8 nodes and X edges, the good batteries can be any combination of 4 nodes among these 8. This means that, in your graph, if you don't have a node between a group of 4 nodes, this means these 4 nodes form a combination of good node for which you will lose (i.e. it is the worst case). So we want to prove what with 6 edges, we have a way to link the node in such a way that there is no group of 4 nodes that doesn't have a link between them (i.e. you win in any cases). This is similar to prove that there is at most 3 nodes that doesn't have a link between them (if you have one more, you have 4).
@@Neckhawker Thanks, I can kinda understand now, but I think it's the terminology that's throwing me off, specifically "node" and "edge". I've seldom if ever heard of "nodes" outside of video game objects and body parts, so I'm a bit confused as to their mathematical meaning. And using "edge" instead of something like "link" or "connector" is strange to me.
@@stevenfallinge7149 I don't think we ever used "edge" as a technical term in Geometry, just the dictionary version; but it has been about 8 years since then, so I could be wrong.
I didn't finish the video but this is my take. 50:50 on dead and good battery. Battery 1 to 8. Test 12,34,56,78. Probability is quite high for one of those to work. If all didn't work. That means it's all 1 good + 1 bad battery combo. Just get 2 random pair and switch their partners. For example 1234. Just test 13,14 + 23,24.
I came up with 7 tests too. I also fairly easily found that you need at maximum only TWO more tests to find ALL the good batteries (there are two branches to check: if you needed didn't get it in 4 tests or if you did. Both could need 9); so unless you are in a hurry, you really ought to do that too!!
Wait... In the 3-3-2 test, we found at most one good battery in each triplets, in the worst case. So, by elimination the remaining two are good for sure. So the 7th test is not required.
There are C(8,4) ways to arrange 4 bad and 4 good batteries in a set of 8. C(8,4) = 70. To write a integer between 1 and 70, 7 bits are needed. Each test provides 1 bit, so we need at least 7 tests. QED
If the problem were to identify the status of every one of the 8 batteries, then we would need to distinguish between 8C4=8×7×6×5/(1×2×3×4)=7×6×5/3=7×2×5=70 possibilities. As 2⁶(=64)
How does each test provide 1 bit? "Each test provides 1 bit" would imply that the outcome of a test would divide the number of still possible distributions by 2 . However, if we'd look at the worst case scenario of the outcome of the first test, it doesn't appear to be true. A priori, there are (8 choose 4) = 70 possible distributions of four good batteries among 8 batteries. When the first test doesn't result in lighting up the flashlight, there are two possible reasons: - there is no good battery among the two first-tested batteries. So all four good batteries are among the 6 yet-untested batteries. The number of possible distributions in this case, is (6 choose 4) = 15 . - there is one good battery and one bad battery among the two first-tested batteries. So there are three good batteries among the 6 yet-untested batteries. The number of possible distributions in this case, is (2 choose 1) * (6 choose 3) = 2 * 20 = 40 . So the number of still possible distributions of the four good batteries among the eight batteries after the unsuccessful first test, is 15 + 40 = 55 . The number before this test was 70 ; from 70 to 55 , that's hardly a division by 2 (or a gaining of 1 bit of information). (If we have performed the second test, then in the worst case scenario, there are still at least 41 possible distributions, which is more than the "remaining" 5 bits could represent since 2^5 is only 32 ; so how would two tests mean that we've gained two bits of information?)
@@paulstelian97 Well, that's not true either. Look at the second 8-tests method in the video (between 7:47 and 10:47 ). After the 6th test fails, there are still 17 possible distributions of the four good batteries: - {1, 2, 3, 4} are all bad, {5, 6, 7, 8} are all good : 1 distribution - {1, 2, 3, 4} are three bad batteries and one good battery, {5, 6, 7, 8} are one bad battery and three good batteries: 4*4 = 16 distributions. At the 7th test, a pair from {5, 6, 7, 8} (let's say (5&6)) is tested. After that test fails, there are 8 possible distributions left: - {1, 2, 3, 4} are three bad batteries and one good battery, {5, 6} is one bad battery and one good battery : 4*2 = 8 possible distributions. So the 7th (failed) test decreased the number of remaining possibilities by a factor greater than 2 (namely, from 17 to 8 )! Or according to the terminology of your/the original commenter's reasoning: the 7th test provided more than 1 bit of information. It appears there is _no basis at all_ to claim that "each test provides (at least/at most/whatever) 1 bit of information".
I always wonder if we can do this kind of problems using Shannon’s theory of info. We start with entropy of C(8,4) and need it to be lower than C(6,2), each experiment would lower the entropy by 1/4 (excluding the case that they both work) etc.
For sure there are links to Information Theory, but using it directly may not be feasible. For example each experiment will give you some amount of information (let's say b bits of info), but will 2 experiments give you 2b bits of information? Nope, they will give you at most 2b bits of info. If you are lucky you may use Shannon theory to prove 6 experiments won't be enough though.
Let a good battery be 1, bad 0. The arrangements of good / bad batteries are "bytes". The number of eligible arrangements is the number of bytes with 4 bits set. This little script does the job of counting them: ``` fourbit = 0 for i in range(256): if i.bit_count() == 4: fourbit += 1 print(fourbit) ``` Turns out, they are 70. Now, 2^6=64, not enough to distinguish between 70 things, but 7 bits are enough. I had figured that 7 is the optimal solution, but I couldn’t find anything better than 8, so pressed play to get the answer.
@@OrangiaNebula If you had to identify all 4 good (or all 4 bad) batteries, then, yes, you would have C(8,4)=70 cases to distinguish, and it would take at least 7 tests to guarantee solving it, no matter what binary tests you have available. However, you only need to find 2 of the 4 good batteries, so, while you know it can't be harder to solve than identifying all 4, it's possible it could be easier. For example, if you already have a battery you know is good, so you're actually testing just one battery at a time, it would only take at most 5 tests to identify 2 good batteries (if only 1 of the 5 is good, then the untested batteries are all good), while it would take up to 7 tests to identify all the batteries. Note that in both scenarios, you'd potentially need an extra step to load the torch with two good batteries.
I came really close to finding the optimal solution on my own! I figured that if you take a group of 6, then there’s guaranteed at least 2 good batteries among them. I split the 6 into 2 groups of 3 and test those trios. if those all fail then I know there’s 1 good battery in each trio. where I biffed it was in trying to find those 2 good batteries instead of realizing what that implied about the 2 I had not used previously 😅
Seven tests are required to 100% get the lowest number of tests all the time BUT it doesn’t account for the random possibility that the first test gets 2 working batteries.
4:28 It's 11 tests, not 23. You don't have to test each battery against *all* of the remaining ones, you only need to test the first 5 against each other. Worst case scenario, this group contains at most 1 good battery, so if all tests fail, 6-7-8 are definitely good. Pick any 2 of them for the final confirmation test & you're done.
@@KatorNia There are several possibilities. The 23-test Method (in the presented order in the video) is: *12* 13 14 15 16 17 *18* , 23 24 25 26 27 *28* , *34* 35 36 *37* 38 , 45 46 *47* 48 , *56* From these 23 tests, we could skip the 16 non-bold tests, and only perform *12* , *18* , *28* , *34* , *37* , *47* , *56* . But *14* , *18* , *23* , *27* , *37* , *48* , *56* also works.
Sure, except you failed to understand the reasoning this was even explained in the first place. This is the brain dead option in which you just brute force without care to test every possible combination. It’s what a child could think of but at least it’s an answer.
@@CrypticCobra That's an artificially created "bad" method. I mean, with that reasoning you may as well test 1-2 & then 2-1, 1-3 & 3-1 etc, to create 46 unnecessary tests instead of 23. I thought we were talking math, where you don't prove the efficiency of a method by intentionally misrepresenting the efficiency of another. _My comment stands._
As a developer, I loled with the first solution, if it was someone I was interviewing I would be just like: "thank you and good luck dude". The obvious rapid solution for me was the second one.
The answer is 6. You only need 6 tests to be sure that you have 2 good batteries in the flashlight. You said it yourself at 12:14 ! That 7th one is unnecessary, it’s not a “test”, you’re already mathematically positive they work.
On my own, I would've solved this in a simpler fashion. I would've done 4 pairs, 1-2, 3-4, 5-6, 7-8. I now know that in each pair there is a good battery, and a bad battery. I can disregard 5 through 8 because I know there's at least two good batteries in 1 through 4. I then would test 1-3, and 1-4. I then test 2-3, and if it's still off, I know that 2-4 is my good pair of batteries.
Wonder how the proof is right if the approach you describe shows you can turn on the lamp on the 6th test. Maybe the proof is for identifying all 4 good batteries?
This was my solution as well. I think we can optimize however. After 12 34 56 we know either 78 is good *or* each pair of batteries has 1 good battery. So 1278 is guaranteed to have 2 good batteries. (3+5 tests bah) What more, 12 34 failed means at most 2 good: so 5678 is guaranteed to have at least 2 good. (2+6 tests bah) 12 23 13 failed means 45678 has at least 3 good. 45 56 46 failed means 78 has at least 2 good. Which ends up with OP's solution. 12 23 34 13 24 14 failed means 5678 has at least 3 good. 56 78 solves it at 6+2=8 samples. 12 23 13 means 45678 has at least 3 good. 45 67 means 8 is good. 48 58 wins. 7 steps, and not the 3 3 2 pigeonhole solution.
@@adamnevraumont4027 Your last 7-step solution is equivalent to the 3 3 2 solution. The first triple is 1-2-3, the second triple is 4-5-8, and the pair is 6-7. You perform the tests in a different order, though, and you used a different way to arrive at the same set of tests. Actually, that's not surprising, as it is likely that all 7-step solutions are equivalent. Anyone cares to prove or disprove that?
@@Aluzky.Irezumi i was thinking this too, but might fall under circumventing the riddle. To be fair, though, i'd tell them they should hire me for my expertise since I seem to know more than them.
You do still end up with 8 tests if you have to lick all of them. Your test is fastest if that's what counts for the riddle. You'd have to hit 4 good batteries along the way and can stop there to match or beat this video's solution.
@@technocolossus dropping in 3s would be considered one test. The drop test is relative to the other batteries. And you'd really only need 2 drops. You could do 4 at a time, but you might not be able to track them all at once
@@technocolossus 5 at most actually. You need to find only two good batteries, even if you get 4 malfunctions in a row, next two are supposed to work. If you get 3 bad batteries and one working, then fifth test will either result in you finding good battery making a good pair or you finding the last broken one, guaranteeing that you can pick any of the last three
I had originally through bad meant the voltage was just low so the pair of 1 good 1 bad wouldn't be enough to use the flashlight but still distinguishable from the pair of 2 bad (i.e. the filament would glow a little). I got to 5 with that assumption but I wonder if there's some clever way to get to 4.
Being a bit pedantic, @11:55, the descriptor for 456 should be "exactly one good and 2 bad" since the 123 tests reveal that one of the 456 batteries must be good (and also now know that one of the 123 batteries must be good)
@@jaideepshekhar4621 he meant that instead of an uncertain, "at least," the video could just have stated the exact numbers, since that's a given at this point.
Here's how I would answer this on a job interview: Bounce them. Drop AA batteries from a decent height and, although I forget if the charged ones bounce and the discharged ones don't or if it's the other way around, you will still be able to separate them into two distinct groups of 4. Then you pick a group at random, and with a single test you'll know if that group is charged or not. You will have then identified not only two working batteries, but all 4 of them in a single test.
That's good domain knowledge, but the bounce test can only consistently tell the difference between totally new batteries and batteries that have been used at all. A battery at 99% charge will bounce similarly to one at 50% charge or 0% charge.
My naive approach is as follows. Split the batteries into two piles of four batteries each, and then test each pair in the first pile (6 tests maximum - 12, 13, 14, 23, 24, 34). Either you find a good pair (you're done) or you don't. If you don't, then we know the first pile contains either only one good battery, or no good batteries. So in the worst case, the second pile contains one bad battery. We can then do one test on pile two, testing 5 and 6 together (test 7). If it does not turn on, we know either 5 or 6 was bad. Therefore, batteries 7 and 8 MUST be good. (test 8) So in my naive approach, 8 tests is worst case. Edit: Oh, turns out that was strategy 2! I feel smart now
You don’t need to do the last test since you already know via process of elimination so it’s 7 😊 By extension of this logic you can actually generalize the answer to n/2+3 tests for n batteries where n is even and half are bad
I think I have a solution in six tests. Consider we select four batteries. If more than one of them is good, then we will need no more than four tests to find the pair (eg 1,2 are good, then 13 and 24 fail, 34 fails but 12 good and we can stop looking). Therefore, if we are still failing after 4 checks, we now know our selection is 1 good and 3 bad or all 4 bad, and thus the remaining unselected batteries must have at lest three good batteries among them. It will require no more than 2 tests to find a good pair. 4 + 2 = 6. QED.
1&3 , 2&4 , 3&4 , and 1&2 could also all fail when {1,4} are two good batteries, or when {2,3} are two good batteries. So no, it's not guaranteed that after the first four tests fail, there would be at least three good batteries among the remaining untested four batteries.
7:25 dont we need to do more tests to find out which 2 good batteries are in 5 6 7 and 8? It took 8 tests to find 2 batteries 2 and 4 12:47 wouldnt we still need to figure which 2 batteries are good out of the 2 pairs of 3?
As the last pair of cells in all the solutions you provided need not to be tested, as it is a certain event that the last pair will light the torch for sure.Thus the minimum no of attempts will be '6'.
Sure, but that's why he said "for the purpose of this puzzle, include placing two good batteries into the flashlight." So in a sense, he turned the puzzle into _"how many replacements are needed before the flashlight can turn on"_ not _"how many tests are needed to find 2 good batteries."_ Same results tho, you just add 1 to every solution.
You have to do the final test to know for certain that the flashlight works. If the flashlight is broken then you haven't actually been testing the batteries, you've been demonstrating that a broken flashlight doesn't work whether it has good batteries or not.
I got asked this once in an interview, after the engineer noticed that I used to run an instrument shop. I told him 1, just needed some resistors and some wire or foil. He called me a liar and ended the interview shortly after. Never asked me how, just bounced me. Five years later he found me on LinkedIn and apologized. It took him that long to realize what I was getting at, and to also summon the courage to talk to me again. He even tried it himself by getting some faulty batteries. Done in one. He promised to buy me a beer, but I was kind of hoping he would refer me to a job. Still aint got that beer.
In real life the flashlight would glow dim with 1 bad & 1 good battery, letting you know that you have a good one, split them into 2 separate piles and then test another pair, if it also glows dim, then leave one and take one from the previous piles, either it will not turn on (swap for the other two), glow dim (swap for the opposite pile) or turn on fully = 3 tests, realistically.
I wonder, is there a general formula to figure out the minimum number of tries to guarantee a working pair? To be precise, is there a formula that will work with any given value for the following variables: nrGoodBatteries, nrBadBatteries, nrNeededBatteriesInFlashlight In the video's example, we're working with nrGoodBatteries=4, nrBadBatteries=4, nrNeededBatteriesInFlashlight=2 Is there a formula that gives us the minimum with, say, 4, 10, 3? Or 12,5,4? Or any arbitrary number for these variables?
"I test 1+2, 3+4, 5+6, 7+8, 1+3 and 1+4 and I'm 93.6% sure. This solution is only mildly significant (p=0.064), exactly like the job you're hiring me for, and that's why I'm the perfect fit"
How in the heck would a scenario emerge where you know for certain there were exactly four bad cells of a batch of eight, but not know which *any of them were in the first place?
A careless person just replaced batteries for his two flashlights, and left the 4 discharged batteries with the remaining 4 good batteries in the drawer.
@@Cowtymsmiesznego that's why I've been exclusively using rechargables for the last 20 years. There are no "bad" batteries in my home. If they're too low to run electronics, they get recharged.
The complexity of the solutions that people have come up with show that this fails as an "interview question": it is unreasonable to expect someone to come up with such a solution from scratch. It is more a puzzle which someone might decide to tackle if they're interested, and might spend many hours on before coming up with something that looks like a solution.
@@rosiefay7283 i came up with a not optimal, but pretty good approach (8 checks worst case) in like 2 minutes from just thinking about the problem. maybe i just got lucky timewise but the parts of the problem space I focused on (i.e which possible permutations exist) led me directly to that approach. that's probably what's being looked for in an interview type of context rather than coming up with the exact optimal solution because you've seen it before -- that's why tech companies' interview questions are always being switched out for new ones
Interview questions aren't about the answer though, more about the problem solving ability of the candidate. The question needs to be worded in a way to encourage that process to be shown, however.
Nope, I figured it out in about 15 seconds. Actually guesstimated it in 4 seconds and took the other 11 to mentally prove it. Coming up with it "from scratch" is exactly the point, that you won't always have someone holding your hand in life, that you need to be able to handle some situations from scratch. Tests like these separate those good at math puzzles from those that aren't, which is the point. If it takes you an hour, your puzzle solving skills OF THIS TYPE are inferior to those who can do it faster, for the employer to find people who are adept at puzzles like that, or else choose a different kind of problem to solve that is more relevant to the employment position, and again, someone not good at that type of problem solving, will take a lot longer than someone who is. Besides as the video stated, some employers won't even care if you reach the most optimal solution, just that you reach one that works. Anyone can do that in a few minutes even if they aren't good at verbally describing it or drawing pictures about it.
It is stipulated that "testing" the final two batteries that you know are good counts. In a worst case scenario, the last combination you plan to test will be the good one.
This is why at 1:20 he specifically says to include the final insertion of two good batteries in the tally. It really doesn't change the puzzle, it just means all solutions would be 1 test fewer. But that's also a nonsensical thing to do, because the goal isn't to find the good batteries it's to turn on the flashlight.
in practice a flashlight will usually produce a dim light with one good and one dead battery. find a pair that doesn't light up at all, then use one of the two confirmed bad ones with the rest in order to find the all of the singles that produce a dim light which you would know are good. then you find all of the good batteries.
I assume the flashlight has some electronics that only run at above 1.8V (0.9V is the regular cutoff voltage for testing regular 1.5V alkaline batteries)
You start off with two containers next to each other. One with fresh batteries, the other with used batteries you know died. Someone knocks over both containers mixing the good and bad batteries with each other
If you're running from the zombies, you don't need to do the final test. So, you do 6 tests and run out with the last two batteries if all 6 failed with confidence that the last two are good.
Or just take all 8 batteries and run to a safe spot. If you can run in the dark eh? You will put in the last 'test' because you need the flashlight on, of you're not in that much of a hurry in the first place. You are of course right that we can conclude it after 6 tests, but that is why it was stated in the intro that the last test counts as 1.
Idk if I’m just avoiding unnecessary number pairing or not, but I’d just drop the batteries a foot above a hard surface. If it bounces an inch or more it’s empty.
The last solution is cool, it's so deceptively simple. I love how because the worst case is assumed, it basically forces the last pair to be good. Even before the 7th test you know it will work. I wonder if the optimal number of tests in the worst case for any even set of n batteries where half are good and half are bad is always n-1. I'm not smart enough to prove this but it sounds right haha.
0:40 "If you have one good battery and one bad battery, the flashlight will not work." That's not how batteries nor flashlights nor electricity works. The simplest, easiest solution is to go buy a dirt cheap battery tester for a couple bucks and then test all of the batteries individually. Or get a slightly more expensive multimeter for $30, which has lots of additional uses outside of battery testing. Now the worst case is that you only need to test ZERO times to "find" all of the dead batteries using the flashlight because you are using the right tool for the job. Thus, the correct answer is ZERO. Use the correct tool for the job and stop asking terrible questions like these in interviews.
Also, if these are 9 volt batteries, you can use your tongue instead. Just touch each battery to your tongue and if you get a strong shock, then it's probably a good battery. If you get little to no shock, then it's bad. Again, no need to use the flashlight at all and thus you've conducted ZERO tests with the flashlight.
Also, there is no such thing as a dead battery. It just might not be storing as much of a charge as you would like it to be storing. This is a bad question because anyone remotely familiar with electronics is going to tear this problem apart for being extremely vague on the specifics.
Depending on the battery and the flashlight, it is possible for it to not glow enough to be seen at 1 good 1 bad. And, the bad battering could be insulators for all we know. Don't apply physics to a reasoning question
There is nothing terrible about this interview question and it's actually quite interesting imo. It shows problem solving in a hypothetical situation which has value.
Loads of errors here. Like 10:35 - no you need 9 tests. You will not know which single of the batteries are bad. You need to test the failed pair against the good pair to single out the bad one.
No, you don’t need the info which of the 4 remaining batteries the bad one is. You know from the previous testing of the first group of 4 that exactly one of the second group of 4 is bad. When you test the first pair of the second group of 4 and the flashlight is off you know that the other pair of the second group of 4 definitely consists of two good batteries. You test the other pair and you know the flashlight is on hence these are two good ones. The problem is solved. It is true that you don’t know which of the first pair of the second group of 4 is bad, but you don’t need to know you already have two good ones.
Actually, you can also slightly alter the method of pairs for a maximum of 7 tests. These are the batteries you need to test: 12, 34, 56, 71, 72, 83, 84 (there are other combinations, this is just one of them) It works because after testing the first 3 pairs together and the flashlight being off, you don’t need to test the last pair to know that there’s at least one good battery in it. It’s either a good and a bad one or two good ones Then, choose one of the batteries of the last pair (7 or 8) and test it with another pair (12, 34 or 56). If the flashlight is still off, choose the remaining battery (7 or 8) and test it against a different pair (it’s important that it’s different) If 7 and 8 were a mixed pair, it works as explained in the video. If 7 and 8 were both good batteries, you choose either one and test it against a pair and if the light isn’t on yet it’s because you accidentally chose the pair with two bad batteries. Just switch batteries (it doesn’t matter cause they’re both good) and test it against a different pair, which will contain a good battery That’s the solution I found. More complicated to explain but pretty simple all things considered. And it will take slightly less attempts on average compared to the method explained in the video
It is the same seven test pairs as in the 7-test procedure in the video, but in a different order (and labeled differently). But indeed, your order is the most efficient order of the 7 pairs, while the video's order is the least efficient order of the 7 pairs. (Less efficient than the presented 8-test solution, even.)
So depending on which job and which test, pretty useful then? If I'm trying to land a probe on mars, I kinda want someone who can solve a brain teaser for maximum efficiency while leaving 0 room for error. If I'm trying to get funding to build my mars probe, I kinda want someone who's at least self aware enough to put the 'correct' answers on a personality test
The tests don’t need to map, just the problem-solving toolset. In fact the tests SHOULDN’T map, because then it’s something that should be part of the training because it’s a solved problem
So... the 7 test method is wrong. Because if you can confirm 1 good battery between 3 batteries, twice, you then have to figure out which of those 3 is good.
Test one group of three: AB, BC and AC Test a different group of three: DE, EF and DF No need to test the remaining batteries. If neither group of three has two working batteries, you know the extra pair is working. If any pair within a group of three worked, you found a working pair. Do one final test with two batteries that have been shown to be good.
In cylindrical batteries, Batteries with more charge bounce very little, while discharged batteries bounce more. This test is performed by dropping batteries on their negative terminal. Therefore, assuming these are the standard cylindrical batteries (aa,aaa,d) drop them on their negative terminals, take the 2 that bounce the least, and this problem is solved in “one test” (by the standards of the problem). 1:45
Realistically, each drop comparison of a pair of batteries is considered "one test", so the fastest solution is two tests with the first pair of batteries bouncing high and being confirmed good in the flashlight. Worst case scenario would be 5 tests (first two tests only contain 3/4 bad batteries, requiring a 4th drop test to determine the 2nd of the four good batteries and then finally the test in the flashlight).
@Tamarocker88 yes you are correct, but by the wording of the video, this would only be technically considered one test, as a test only occurs when batteries are inserted into the flashlight and it is turned on. If you want to constitute a drop of batteries as a test, then depending on how many you drop at once you would be correct. I just said it was technically one test due to the phrasing of the problem
This. Just drop them and observe. Simple.
they said one test is two batteries in the torch@@Tamarocker88
If my boss won't let me use my multi-meter I need a new job.
You need a new boss!!!
Solution: Replace boss.
New problem: There was a mixup at the multimeter factory and your multimeter came with 8 batteries...
@@eman2867 And half of the probes have a broken wire inside.
@@eman2867 Well played!
0:06 Due to a manufacturing defect = You tried to use batteries from your junk drawer that have been in there for at least 15 years.
Well, there is the manufacturing date and the guaranteed usage date on every battery nowadays. If it does not have any of these dates, best to get rid of them. 😉
Wait, there’s dates on your batteries? All mine say is “ _D __-o-__ _*_n_** t* -R- _3 _*_C_** h* a -r- _ge_ “
@@charliethunkman I just have a 9V block battery here, lithium cells, and the "BEST BEFORE" date reads "12-2027"
No production date, although this I have seen on batteries as well.
😂
I started thinking of the problem before watching the video and went down a similar path where the were 3 possible states bright-dim-off. He did however specify that it was a manufacturing error so its not necessarily the case of the traditional idea of a dead battery. For all we know the electrolyte could have been replaced with bubblegum.
Zero tests needed. Throw away all 8 batteries and get four new ones bc an engineer's time is worth more than four batteries.
You mean safely dispose of those batteries.
@@robcoop6521 I didn't say throw them away in an unsafe manner.
I mean, the setup implies that someone already tested all the batteries and didn’t toss the duds, so this isn’t a top-shelf employer.
1. I climbed up the mast to change the batteries in my home weather station.
2. I carried four good batteries in my pocket.
3. I took out the bad batteries.
4. I put them in my pocket.
5. ... *bad words*
@@galfiskCFS
sr. software dev here. i got the two ways to test 8 on my own, but not the 7 test technique. very interesting and helpful. thanks! 🏆
Interviwer presents the problem:
I produce the flashlight from my pocket. ( i always carry one.) And ask what kind of opperation are they running. Why have you allowed bad batteries to contaminate the stock of good batteries? I throw all the batteries out and explain the cost of the time to test these batteries exceeds the cost of four new batteries. I instruct them to buy new batteries out of which i will replace my batteries when they arrive. Go on to explain how ro implement a procedure to avoid such a situation in the future and issue an invoice for a $300 consultation fee.
Right, but you need the flashlight right now to fix something right now, not tomorrow when the stores open, or 30 minutes from now when you get back from 7-11 or some other all night battery selling place. The cost of not fixing it right now vastly exceeds whatever you are going on about.
@@dirkbester9050 which is why I carry one everyday.
And that is why governments overspend.
aaaaaaaand... you've failed the job interview
You're failing to consider the cost of the time it takes to acquire new batteries in your analysis. So long as the testing time is shorter than the time it takes to go to the shop and buy new batteries, introducing the cost of time properly favours testing.
If your battery supplier has a defect rate of 50% you might want to consider a different supplier.
7 worst case btw.
Gow do you get 7? Max 5
@@tigerboy4705So how did you get 5?
@myster4775 by commenzing way too early and missunderstanding the puzzle xD (didn't get that the flashlight needs 2 batteries xd)
They are from a bad batch and you need to defeat the dark presence, and it's faster to dump out the batteries than pull them out one at a time, and you are sorely lacking time. There, wrote you a half decent plot.
The number of times I've had to deal with customers mixing old light bulbs with new light bulbs.....a very similar sort of problem, except I don't actually know how many (if any!) good bulbs there are.
An efficient way to sort them out is very practical.
Older two-lamp fluorescent fixtures often require two good bulbs in place to function.
The first example did more tests than was needed with that method.
After testing 1 with 2 to 6, and the flashlight didn't turn on, there is no need to test with 7 and 8, as you must have tested 1 with at least one good battery in the other slot, and since the flashlight didn't turn on, 1 must be bad.
Completely true
But also remember that the whole point of the first solution was to just get _a_ solution that works. We already knew it was terrible and we were okay with that
It's probably a good idea to get in the habit of just letting the bad solution be bad, and not trying to tweak it or optimizing it. That's no point spending time on that when you're going to replace the entire thing with a completely different approach in a minute
(Obviously in this case, that doesn't matter. It's not like this optimization took a lot of time. I did the exact same thing myself when I was looking for an upper bound)
still needed to test the 7 and 8 because there is still a probability 7 and 8 are both good batteries
@@daudnobel since you know there are four good batteries, once you've tested it with 2 through 6, you know 1 is bad. While 7 or 8 might be good, if 1 is good, you'll have found another good battery from batteries 2 through 6. As has been pointed out though, this wasn't intended to be an optimal solution.
Came here to post that.
The other test rounds can be shortened by 2 as well.
The first and second strategies are actually the same strategy, just in a different order. When you choose two pairs from the first strategy and test them against each other, that's the same as the group of 4 in the second strategy.
The order in the first strategy is about 20% more efficient (in terms of "average"/expected number of tests) than the order in the second strategy, though.
In fact, the first strategy is more efficient than the 7-test method as presented in the video.
The first test is a matrix search and the last test is a tree search. Tree search is always fastest as you can always eliminate half each time.
None of the presented methods in the video always eliminates half at each test.
@@yurenchu its a battery u test 1 on lips if its charged u keep it, if its dead u toss it. u check next battery on lips if its charged, flashlight has 2 battery's if neither was charged ur 2 bad battery's down 4 good 2 bad to go, continue testing at worst it will take 5 tests to know the rest are good/bad/ identify the 2 groups of battery
you can also bounce them, charged batterys have more bounce.
alternatively you could use a multimeter or many batterys today have a charge bar on side of them for ppl that dont know how to test them with there tounge
NO electrician ever sat there with a pile of batterys putting them in at random to find out which ones where charged.
theirs a number of ways of detecting charge level they would use one of them before they resorted to testing with a flashlight in groups of 2, they would at least use a flashlight that held 1 at a time reducing the number of tests to 5 from 11 if you do it with 2 and ur loading 1/2 as many each time also/half the time per test
@@violetquinnlaw The original commenter and I were talking about the methods that were presented in the video, not about what kinds of stunt experiments Johnny Knoxville (or Adam Savage) would do with a bunch of batteries.
Furthermore, the question in this video is meant as a logic puzzle, not as a test for the recruitment/hiring of electricians. The principles in this logic puzzle can be used in/extended to all kinds of (data) filtering and (abstract) sorting problems, the "flashlight" and "batteries" are just the dressing up of the problem to make the conditions of the problem more accessible to the general viewership of this math/puzzle channel.
Likewise, the so-called "Secretary Problem" is not really about hiring secretaries, and the famous "Monty Hall Problem" does not really apply to any real game show.
Bubble sort never failed me and patients is a virtue for those who asked me for A solution.
I would Split them in two groups of four, test all the combinations in one group, if none of those work It means there's a maximum of one good battery in that group. Then start testing the second group, It would take at most two tests to single out the faulty battery in the second group. So at most It would take 8 tests in total, in the worth case scenario.
Plot Twist: The bulb is burnt out.
That's why you need the final test to prove that you've actually been testing the batteries, not the flashlight.
what if all batteries were bad? You could theoretically never know.
Polarity diagram on the flashlight is backwards.
Real story: My parents were setting up a 3-way switching. They tested it and it didn't work out. So they searched the error, didn't find any, tested and tested and searched and searched. They tried replacing the bulb, they even tried replacing the light base. In the end, it turned out, they used two bad bulbs AND two bad light bases and the 3-way switching was set up correctly from the start.
By the time you figured that out, you had been fired.
In the first example the maximum number of tests should be 15 i think. After 5 tests you will know if your first battery is good or not. You will have to have hit at least one good battery at that point and if the flashlight never turned on then your first battery is clearly dead. There is no need to continue testing that battery.
oh snap, was wondering what you're talking about and suddenly, yep, that makes sense. In worst case scenario the last 4 batteries will be good, not need to test against all 4.
nice catch
Great observation! To be fair, 23 is correct for an upper bound. But then so is 100!
Yeah but 100! is a little too high to be useful, right?
@@jerkison Agreed. TBH, I meant 100 with an exclamation mark, but I left it as is to make it also look like a factorial. Even 100 is not a particularly good upper bound.
in 16 test you find all 4 good batteries.
missed the opportunity to call half of them baderies
or half of them gooderies!
It sounds a bit too similar to the way "batteries" is usually pronounced to differentiate.
He's an American, so "batteries" is always going to sound like "badderies"
Joke so bad I think you committed "assault" and "badery"
i am sure you will be a good Dad hahaha XD
nice dad jokes there :3
I chose the splitting into two groups of four method first because I was a computer service engineer and if you are trying to find a faulty component in a group you can speed up the process by using the 'half split' technique. I quickly found 8 as the minimum.
Apart from it's not the minimum
Split in two groups one 3 and one 5 and see how many test you need.
My mind immediately came up with strategy 1, though I suspected you could get by with 1 or maybe 2 less tests. Fascinating video thanks
The optimal construct can be summarized using elementary school Olympiad technics: pigeonhole principal.
We have 4 good batteries split into 3 groups of size 3, 3, 2, then at least one group has a pair of good batteries.
Then we check *every* pairs inside each group, that's total 7 pairs to check.
This was on TED-ED. In case you're wondering which video, it's the Giant Iron Riddle.
Oh THAT'S why this reminded me of the sock pair riddle.
I remember the pigeonhole principle being taught to me by a programming teacher (in the context of data structures, iirc), and while I was trying to think of why the optimal solution worked the way it did, that's what I remembered. Interesting to see the exact same term come up in a different context.
Why not 8?? I thought this gonna be C(8,2)*C(7,2) or something? Kinda dislike pigeonhole problem because we need to model the problem first, and that is so difficult
@@arolimarcellinus8541 By splitting the batteries into distinct groups of 3, 3, and 2, the first two groups only have C(3,2) combinations per group to check. Worst case scenario, after six tests none of them light, indicating that each group has 2 dead batteries 1 good, thus by definition the group of 2 must be good.
It's basically a variant of the classic "Find the counterfeit coin using only a balance scale" puzzle, except here there are four counterfeit coins and you can only weigh two coins at a time. Surprisingly, even given these differences, the solution turns out to be remarkably similar.
Exactly what I thought
except u can just touch a battery between lips and it it tingles its got a charge. no need to fiddle about with a flash light
It's thanks to my familiarity with this puzzle that I had the idea of splitting up the batteries into two groups of 4, then intuitively decided 2 groups of 3 and a pair was much more manageable probability-wise. I forgot how to solve the coin puzzle though so I was flying blind but it turns out I was on the right track 😅
I think you can use your mouth to solve both questions with varying dangers to your health
Another solution is dividing the group in 3+5. If the pairs of the 1st group (3) are off that means worst case there is one good and others bad and the group of 5 has 2 bad and 3 good batteries (total 3 tries). Then take the 2nd group and do 2 pairs (4+5 and 6+7), both are off means both the subgroups have one good and one bad battery and the 8th one is good (total 5 tries). Now take the 8 and pair with 4 and 5 (total 7 tries).
This is definitely inventive, and also completely correct, so I'm impressed. But I wonder if you've noticed that it's fundamentally the same as the solution in the video? It's just in a different order
If you look closely, you'll see that you test {6,7} as a pair, and then you never test either of those batteries with anything else. So your group of five is actually a group of two{6,7} and a separate group of three {4,5,8}
You also test all three possible combinations of {4,5,8} ( You test {4,5}, {4,8}, and {5-8}). So you're doing a trio, another trio, and a pair, just like in the video
@@douglaswolfen7820 Exactly. I was going for the 3 and 5, and after the 6th test I decided I needed to test 4-5, 5-6 and 4-6 in stead of 6-7 to get the second 2/3 bad ones. So the groups became 1-3, 4-6 and 7+8.
This is actually the same tests as the video’s solution. Your groups are just 123 and 678, rather than 123 and 456.
Perhaps it's even better because the average value is lower
Looking at probability in this problem isn’t very interesting because there’s always a chance that the first pair you try will be right. Deducing that the minimum number of tests needed with perfect luck is one isn’t very hard.
Not sure if this is optimal but my solution would be:
Group the batteries into 4 pairs and try every pair. 1 & 2, 3 & 4, etc. (4 tests)
Either: one of the pairs will have 2 good batteries (and work, thus you are done); or, all 4 pairs have exactly 1 good and 1 bad battery. (If any pair has 2 _bad_ batteries, it necessarily requires there to be at least one pair that had two _good_ batteries, so if none of the pairs just worked, then we have already ruled this out.)
So in the worst case scenario, we've conducted 4 tests and we now know that each pair of batteries that we tested must have 1 good and 1 bad battery. Take any two pairs; call a pair "AB". Test 1 battery from each pair; there are 4 possible permutations: AA, AB, BA, BB. As we know that each pair has 1 good battery, exactly 1 of these permutations will match up the two good batteries.
It should take no more than 8 attempts to get 2 batteries that work.
correct me if i'm wrong: shouldn't take more than 6 attempts, really . after trying out the first 4 combinations, pick any two pairs (each pair should have a bad and a good battery) and do two more tests with one battery from each pair. One of them must have 2 good batteries
@@thejaskodoth4630 Two pairs that each contain 1 good & 1 bad battery have 4 possible arrangements, and only 1 of them puts the 2 good batteries together.
If you test one battery from each pair and it _doesn't_ work, then there's a 1/3 chance that you happened to pick the 2 bad batteries - in which case using the _other_ 2 batteries will be the good combination. But the other 2/3 chance is that one battery was good and one was bad, and you don't know which is which, so you may have to exhaust all 4 combinations to find the good pair.
Take the two pairs with one good amd one bad battery.. let them be a0,a1 and b0,b1.. test a0 with b0 nd b1. If we a0 was a good battery we would have got a good pair.. (
Elegant solution, I didnt find the 7 tries one, only 8 tries solution.
But, what if the challenge is to find two working batteries as fast as possible, is it still better? My hunch without pen and paper is that the 8 solution requires fewer tries on average than the 7 one?
@@ShankarUtthandyV it only takes 6 tries because by powers of deduction, if none of your 6 tests lit up, then the remaining untested pair must be good, no test needed.
I GOT THE 7-TEST SOLUTION!
my initial solution was 10 tests, but i misunderstood the question for longer than i’d like to admit (thought we were trying to sort the batteries)
once i understood the question i came up with the 7-test solution while you were explaining solution 2.
Haven't watched the video yet, but I think you can do it in 6 tests:
-Divide the batteries into 4 pairs, and test each pair. If no pair works, that means each pair was a good/bad pair.
-Take two good/bad pairs, and you know there are 2 good batteries within that. Test each battery with its corresponding partner in the other pair.
-Realize that there are still some untested pairings, and it's probably going to take a total of 7 tests.
_edit:_
_Ok, it looks like this actually takes 8 tests_
I came to this conclusion as well before watching the video, and I believe you can still count this as 7 tests, because if you complete the 7th test without finding a pair of good batteries, you don’t actually have to perform the 8th test since it’s guaranteed that the remaining pair are good batteries.
I attacked it in the same way, and think 6 is the minimum. Check my work! You don't need to do an additional 7th test if none of them light up, because using deductive logic, the remaining pair after 6 rounds of tests must be 2 good batteries.
Please check my logic I think I did it in 6 on my first try, and with multiple pathways!
Test 1: 1+2
Test 2: 3+4
Test 3: 5+6
Test 4: 7+8
If any of them lit up, you found your good pair in the first 1-4 tests by pure luck.
If none lit up, then each pair should have one good, one bad.
Test 5: 1+3 = good + good, or bad + bad, or bad + good. If light, you won by #5.
Test 6: 1+4 or 2+3 = if either test lights, you win, if they stay dim, you know the remaining pair is 2 good batteries, and you still win.
@@petertrzos6645 Ah, this a good thought process, the logic being that you use the first 4 tests as a way to obtain 4 good+bad pairs, and then you only need to use 2 good+bad pairs to determine the 2 good batteries within them. However, I disagree that this requires only 2 additional tests for a total of 6 tests. To be explicit with the possibilities, there are 3 cases when taking (1, 2) and (3, 4) as the 2 good+bad pairs and finding that (1, 3) fails the 5th test:
Case 1: 1 is good, 3 is bad. Then (1, 4) cannot fail the 6th test because we know 2 must be bad from the 1st test, leaving 4 as the remaining good battery.
Case 2: 1 is bad, 3 is good. Then (1, 4) will fail the 6th test, leaving (2, 3) as the pair of good batteries.
Case 3: 1 is bad, 3 is bad. Then (1, 4) will fail the 6th test, leaving (2, 4) as the pair of good batteries.
By doing the exact same procedure with (1, 3) as the 5th test and (1, 4) as the 6th test, the “remaining pair” you mention is ambiguous, since we encounter 2 possible outcomes when the 6th test fails: (2, 3) as the good pair in case 2, or (2, 4) as the good pair in case 3. I do agree that you have a singular“remaining battery” that need not be tested (battery #2), but we still end up needing to find which battery in (3, 4) to pair it with; to differentiate them, we will require one final, 7th test. Ultimately, what you already state for your 6th test (“1+4 or 2+3”) will need to split into 2 tests. Let me know what you think!
@@petertrzos6645 If 1+3 is dark, and then 2+3 is also dark, you do know that 4 _must_ be good (and 3 was bad), but you still don't know whether 1 or 2 was the good one. The 1+4 and 2+4 tests are still required.
You can argue that after the 7th test, you "know" now, but you still _technically_ haven't lit the flashlight yet. I don't know if that means you have to count the last pairing. 8 "battery insertions" before the light turns on, worst-case scenario.
So depending on the definition of success, 7 or 8 tests.
Try dropping the batteries and seeing if they bounce ;)
Science over Math 😂😂😂
Even if the bounce test was anything more than urban legend (and scientific testing has demonstrated that that’s all it is), that test wouldn’t necessarily apply to mismanufactured batteries, only to drained vs charged batteries.
But I did like the humor of your comment. 😅
My explanation of 7 being the minimum is that in Testing 2 at a time, the most we can hope is to eliminate one possibility per test. We have 8 batteries so best case is 7 eliminated needing 7 tests.
I know what you mean, but he kinda thought about this and ruled it out at 0:24 from this imaginary thought experiment.
@@verkuilbthat’s not true. It has been repeatedly shown that dead batteries do bounce higher. It may not accurately tell you if it is dead or just has a low charge, but a used battery will bounce higher than a new one.
Really fun puzzle!
As an additional note, I think you can also show that 6 tests is never enough with simple brute-force coding:
1. Generate all possible combinations of good and bad batteries. There are a total of 70 such combinations (8 choose 4).
2. Generate all possible combinations of 6 tests. There are a total of 376 740 such combinations: 28 possible tests (8 choose 2), which gives "28 choose 6" = 376 740.
3. Then execute each 6-test combination for each combination of good and bad batteries.
4. As the end result, you should see that for all 6-test combination, there will be at least one combination of good and bad batteries where all tests leave the flashlight unlit.
5. This is a total of 26 371 800 (376 740 * 70), which should be easily doable for a computer.
Quite an ugly way of doing it, but still a valid proof. (But I still prefer a nicer proof via graphs).
I solved the problem on my own and I got 6 tests including the final one:
First, I compare them pairwise.
b1 + b2 = false
b3 + b4 = false
b5 + b6 = false
b7 + b8 = false
Where I note that b is the battery and the number on the right is its index
Given the worst-case result, we will find no working result, this is possible with one of two combinations:
1 - t | f
2 - f | t
3 - t | f
4 - f | t
5 - t | f
6 - f | t
7 - t | f
8 - f | t
That is, t - true and f - false will always alternate through 1
Next I start checking through the 1 index
b1 + b3 = false
b2 + b4 = true
Given that we have a failed layout where b1 + b3 will not be true, we get that together with the successful test b2 +b4 we have used 4+2 = 6 tests
@@nixhalla3uk27 In case you did not watch the full video and explanations, your solution does not actually account for worst case as you missed 2.
If b1 is false, b2 is true, b3 is true and b4 is false, then b1+b2 and b3+b4 would be false.
Then, b1+b3 (false + true) and b2+b4 (true + false) would also both be false.
Next, b1+b4 (false + false) would be the final false pair before b2 + b3 (true + true) would get tested.
ah comp sci vs math, get it done or get it done while writing a paper
@bok4822 see my example in the comments. The answer is "6 tests". Logic allows imputed tests that the graphing solution cannot detect. One battery does not get tested and does not need to be tested.
and yet if u used a single battery flashlight or tested it on your tounge by bouncing it or with a multimeter it would be 5 tests of a single batterys not 2 MAXIMUM :P
I worked out the initial 23, then got a solution with 11 and thought it was such an improvement that I didn't need to look further. Lesson learned.
Cool problem! I first jumped to the 4 groups of 2 approach, then after those fail in the worst case, working with just two of those groups. Once I saw the optimal solution, I immediately saw it in terms of combinations. the 8 step approaches being 4 * (2 choose 2) + (4 choose 2) - 2 and (4 choose 2) + 2 * (2 choose 2). The optimal solution being 2 * (3 choose 2) + (2 choose 2) cleverly removes one step, but I feel like it's easy to skip it in consideration due to dividing them into varying group sizes.
Solution: lick finger, hold onto negative terminal, lick positive terminal... if you can feel tingle, it's a good Battery.
actually, it's still bad, just good enough to tingle.
@@mr.cauliflower3536Also, 1.5V might be a little too low for you to "taste" the energy. 🤔
@@mr.cauliflower3536 So now you have to figure out how much tingle does a good battery give, and how much tingle for a bad battery. Maybe this will be the next test question.
@@ralfbauerfeind8236 No, I've been using the 'taste' test for penlight batteries for over 35 years now ever since I was a teen. Empty batteries don't taste. Batteries with charge tast sour. You just press the back (- pole) to the inside of your upper lip and put your tongue on the tip (+ pole)
@PhoenixNL72-DEGA- Same here, it works.
My gut led me to 8 tests Presh presented as solution 2. I don't think I would've gotten the 7 test solution if thought about it longer. Interesting problem.
@@3057luis I definitely felt okay about defaulting to the 2nd 8 test solution, but looking back I kick myself a little bit for not having the mind to find the 7 test, most correct answer.
The two corollaries I derived from the rules that led me to the 2nd 8 test were:
a) a negative test only proves 1 of the 2 tested is bad
therefore b) "grouping" batteries and exhausting the tests within that group will prove that all but 1 within the group are bad
The first corollary I stated is fairly obvious. The second less so, but still not that difficult. Where I failed is not putting much thought into finding the optimal groupings. I approached it as simply as I could -- "we start with an even number, so let's split in half" >>4+4 "still even numbers, so let's split in half again" >>2+2+2+2 "revert back and crunch the numbers" >>4+4>>6+2 tests. I don't think I would've thought to think outside the box with uneven groupings with 3+3+2, even though it was the only other sensible groupings to evaluate.
Oddly, thinking about how I think, I do think I would've gotten to an optimal solution if the starting number of batteries was different. Say 10 for example where 5 are bad, or an odd number of batteries where roundup or rounddown(n/2) are bad. I think my thought process seemed to get stuck in the comfort of 8 total being a power of 2, so I didn't consider groupings that weren't also powers of 2.
Same here, I thought of forming 4 pairs to test right away, calculated that it needs a max of 8 tests, this seemed good enough so I pressed play.
If somebody told me "7-test solutions exist, if you find one yourself you win $1 million" I'd probably find one eventually, but if I'm given this as an interview question I'm happily stopping at 8.
only 6 tests needed , and it's a very simple task . I'm happy i solved it straight away in my mind. Obviously 2 groups of 3 items each and 2 items aside ( and there no need at all to test this 2 batteries ). In case if both batteries are good in the group of 2 , the other 2 good batteries may be placed only in 2 ways : 1) both are in one group of 3 and you will pick them up while doing tests in this group , or 2) each battery in each group of 3 , in this case there will be no working torch in all 6 tests. So you will come to the conclusion that the 2 batteries which were put aside in group of 2 are the good ones without any extra test. In all other cases if you put aside (in the group of 2) only 1 good battery or no good batteries at all, you 'll pick up the working pair during your 6 tests in the 2 groups of 3 batteries each
Reply
It takes 7 tests because the prompt says to include a verification test. Even though this method will assure tha the group of two are both good once you exhaust tests in both groups of three, you still have to "test" the group of two to verify.
14:20 The proof has a gap that I'm sure is fillable, but should be filled: It assumes there is a group of 3 completely disconnected, the group that he "WLOG" chooses 1,2,3. Instead, he should say that this group should exist because: there 8 choose 3=56 groups of three nodes. Each edge can add to 6 groups, when you associate it with the other 6 nodes. So with 6 edges, one can add 6*6=36. However, then one group of 3 must sum less than 1, so that's the disconnected group. In fact, this argument would work with 9 edges, still there has to be a group of 3 disconnected, since 9*6=54
I'm too old to understand what the meaning of edge is
@@andyp5899 yeah - the first solution was waay too simply explained and when he went to "graph theory" i was hoping we'd get a simple explanation too but then it was all verbal and no pictures - very bad made the video less effective for me
Thank you! That assumption was driving me nuts. Something just felt off in the proof by contradiction and it took me a few minutes of restating the proof more formally in my head, to put a finger on it. Then I scrolled down, and sure enough, someone had pointed it out in the comments.
@@physicssquirrel Yeah, I spotted the hole while I was waiting for him to explain the rest of the proof once he'd pointed out that 4 had to have an edge to 123 and I'd had my "aha!" moment.
I did come up with an alternate patch for the hole:
Definition: an "induced subgraph" is the graph you get by taking a subset of the nodes from a graph, along with all the edges of that parent graph that directly connect pairs of nodes in that subset.
There must be at least one edgeless induced subgraph with 1 node since the unique graph with 1 node has no edges.
There must be at least one edgeless induced subgraph with 2 nodes since when you take any node, there are 7 other nodes, so 7 potential edges to the first node, but you only have 6 edges available.
There must be at least one edgeless induced subgraph with 3 nodes since, taking any edgeless pair of nodes, each of the other 6 nodes has to be connected to at least one of those 2 by an edge to avoid forming an edgeless 3 node induced subgraph, but then there are no edges left to connect any of those 6 nodes to each other.
This approach requires more thought for induced subgraphs with more than half the parent graph's nodes since you can't just look for subgraphs among "the rest" of the nodes - after taking an edgeless group of 4 nodes, you have 4 nodes left, so forming a group of 5 that must be edgeless has to include at least one of the first 4...
I'm pretty proud of myself on this one. I'm usually stumped by your puzzles, but I got the optimal method right away for this.
I think I found the seven solution. Putting it in comments before I see the solutions:
12,13,23,78,76,86,45
I initially found a solution that required 10. I decided to try again once I heard the actual optimal numbers. It’s funny how much easier it becomes once you have a goal number.
Seeing the proof at the ending was interesting, because that’s exactly how I figured it out. I drew out the 8 batteries, and looked for a way I could connect them with 7 lines, with no groups of 4 not connected.
I've never been in an interview where a question like this was asked, but it seems like the amount of time that would be given to answer wouldn't be sufficient to figure out the best answer. So, it just becomes a game of, "Did you Google common interview questions and memorize the answers before hand?"
During the test say, I'll google that for you.
already have a light and I don't buy dodgy batteries since I'm not useless.
You don't need to solve it, they just want to hear you try to work it out. It's an interview, not a test. They know you could just Google it, and they already know the answer. The question is if you have a problem in the future while working for them, and the answer isn't known, are you the sort of person that gives up when you find the first solution no matter how bad it is? Do you get frustrated? Or on the other hand, do you hold on trying and trying refusing to give up until you've found the ideal solution at the cost of wasting a ton of time better spent doing something else? There's a ton someone could learn from watching you try to solve this. Probably if you answer 23, you aren't getting the job. If you answer 15, then it depends on how you thought about it and how you responded. If you get 8 in a reasonable time, they are going to be impressed. If you get 7, they will assume you memorized the answer 😉
@@Lord_zeelthey don't actually know you can google anything.... I've had to fire people who didn't know how to use google, and they were young lads.
It took me maybe 5 minutes to come up with a way to do it in no more than 8 steps.
The key is to understand that if you pair up the 8 batteries into 4 pairs, there are only two possibilities: either at least one pair will contain two good batteries, or every pair contains 1 good and 1 bad battery.
If every pair contains 1 good and 1 bad battery, then just take any two pairs and try all 4 possible ways to take 1 battery from each pair to find two good batteries.
Duracell gonna sue for using their trademarked color scheme and saying half their batteries are bad. 😂
Half of the Duracell's batteries are not bad!
This is extremely unlikely to be found infringing, at least because Presh is not advertising any batteries for sale.
Duracell leak. I will not buy them anymore.
Change it to Energizer, then it will be true! LOL.
They aren't dead, they're leaky! Get it right!
I started from the beginning thinking the task was find the good (or bad) batteries. Very different than just most tests required to find 2 good!
Nice problem and nice explanation of various solutions. I am glad that the first solution came to my mind required 7 tests. But the solution is a bit different than the one that you mentioned. Here is my solution, test pair of batteries like 1-2, 3-4, 5-6, 7-8. Assuming non of these passed, now we know that each pair has a bad battery. Take first two pairs and test 1-3. If it fails then we know that battery 2 and 3 both are good or both are bad because both failed with battery 1. Now we test 2-3 and assuming that both are bad, the test fails. Now test 1 and 3, the test should pass. So in total we did 7 tests (including the passing one).
Agreed, this is only something a mathematician would care about. A multimeter is a tool we all have. This test to ferret out candidates will give you a student, not an employee with experience.
Tech employees don't have to logically solve problems? This is news to me
Around the 14:30 mark, there seems to be a jump in reasoning. It's stated that there is a group with at most 3 nodes with no edges between them. We then continue for the proof by assuming that there is a group with exactly 3 nodes with no edges between them.
Note that this can easily be remedied but in the video this step seems a bit off.
In the basic approach 2:30 I am surprised that you tested the first battery with all the others. You can just test it with other 5 ones and that is sufficient. Any 5 batteries include at least a good one, you don't need all of them to guarantee the existence of a good one.
And this continues down the line. You never need to test against 7 and 8 because you will already have ruled out some batteries as bad
So, testing with 6 batteries is the minimum and in the worst case you will have to test 15 times.
Thanks for opening my eyes to a simple
Isn't that assuming battery 1 is good?
He did that on purpose because option 1 was suppose to be the brain dead brute force method that is “better than nothing”
What is the solution to the general problem N batteries, M of which must be in the torch for a test. With G good and B bad batteries ?
Absolutely!
And while we’re at it…
What happens if you pull the wires out of the flashlight, and require so that in your test, the batteries are in parallel instead of in series? And what about if you line up three batteries in series-will the flashlight work with only two good batteries, or do you need three in that case?
In the case of (B+1)*M =
Try 'F' for Fail!
What about X working batteries, Y broken batteries and Z places for a batteries in the flashlight?
Preliminary solution: if there are N good batteries, divide the batteries into N-1 groups. At least 1 of the groups must have 2 good batteries.
Great explanation, but I think there’s a flaw in the proof by contradiction for the 6 comparisons. It doesn’t fully cover cases where only 1 or 2 nodes are unconnected, which could affect the outcome. To be thorough, it would need to address these scenarios to confirm 6 comparisons aren’t enough. Still, an interesting puzzle!
The graphing solution is incorrect because logic allows imputed testing (i.e. deduction).
In the pairs test you only need 7 tests, not 8. Consider 12, 34, 56 and 78 all tested "off". Then you test 23, 45. Suppose they tested "off". Then the next test will be "on". Total 7 tests. edit: correct solution is 7 tests, but you test 23 and if it fails test 24. It will work. Thanks erendorn.
I don't think this is right. What would the next test be after 23, 45?
Maybe we could say 67 should be the next test, but 67 could still fail if the functioning batteries were 1, 4, 6, and 8.
Maybe we could say 18 should be the next test, but 18 could still fail if the functioning batteries were 1, 3, 5, and 7.
Maybe we could say 25 (the only untested pair of 2, 3, 4, and 5), but 25 could still fail if the functioning batteries were 1, 3, 6, 8.
You're right. I wrongly assumed that when testing 23 and 45 it had to be four dead batteries if the test was off, but that's not true.
You can test 13, 14, if still off then 2 is good. Test 23, if still off then 4 is good. You picked the wrong tests, but you are still correct that only 7 tests are needed with pairs.
The thing is sometimes only 7 tests are needed, but in the worst case scenario, which is the problem asked, it can require 8 tests, unfortunately.
@@NesrocksGamingVideos no, worst case is 7. You need at worst 4 tests with the 4 pairs, as per your initial post. If they all tested off, then you know that one of 12 is good, and one of 34 is good. So you test 13 and 14, if both fail, you know that 1 is bad, and so 2 is good. Then you test 23. If it works, then 23 is good, if it doesn't, 24 has to be good. You don't have to do a 4th test.
This was a really cool one!! Thanks a bunch for sharing!!
If you phrase the question as "how many tests do you have to perform to know which two batteries are good?" then the answer is 6 because you don't have to perform the last test to know that the last two are good batteries.
It doesn't make a difference if you rephrase, you didn't need the last test anyway, because of the task's conditions that say there are only 4 bad batteries, so the last one always has to succeed. It would only make sense as a demonstration that the method works, but that's not how you solve math problems...
@@Fossil_Frank Or to put it another way: The puzzle works equally well if we don't count the final "test", but all that would do is reduce the number of tests for any method by one, which is a meaningless difference. Furthermore, if the goal is to make the flashlight WORK we still must insert two good batteries. Merely knowing that there ARE two good batteries is insufficient. Or to put it one more way: Only a mathematician would be happy with a 6 test solution, and will then sit in the dark feeling smug.
@@Lord_zeel First of it's not the goal, the task asks how many tests are needed and therefore, the provided anwser is wrong. Second, it does make a difference. Imagine you add a needless coloring to the Four Color Algorithm. Suddenly, you can't go below 5 colors in any planar graph, which would at best make your applications of it crap, or if everyone adapts it : there would be unpleasant implications on a lot of technology you use daily. Furthermore, this argument refers to practicality, but let's be honest here: would you really devise a method for minimizing tests here, instead of just testing at random until you find a working pair? It'll certainly be faster than coming up with a clever solution and it's not like anyone tests batteries like that. So no, that kind of mindset doesn't make sense.
It doesn't seem like you have a science background, so you may not be aware, but these kinds of problems form classes that when generalized, provide valuable insight into things you'd never think related. Also, while this is a (deliberately) trivialized scenario, so that it refers to concepts everyone is familiar with, most real solutions can't be easily empirically verified in general, many can't at all. For example, how do you check empirically if the before mentioned Four Color Theorem really holds? By testing it on all planar graphs? There's an ininite amount of them. This is the whole reason people stress about mathemathical rigour and minimalistic solutions, while also not caring at all about steps to "show" that they work - you're supposed to be convinced of that by analyzing the method itself and it's proof. If that's not enough then you either don't understand it, or there's actually something wrong with it.
@@Lord_zeelA mathematician, or a supply chain person in a lit room, who can ship the batteries without a qualm to whoever needs them, or someone doing maintenance checks, etc. There are plenty of people interested in something being ready for later use that are fine not using what they’re testing
He did specify that the final insertion counts as a test. This does not fundamentally alter the difficulty of the problem, it just adds one to the optimal count.
"There is a smarter testing procedure that will get an answer in only 8 tests"
Me: Yes!
"And this is only 1 short of the optimal number of 7"
Me: Dammit!
Same. Once I knew there was an optimal of 7 tests, I could find it, but my first idea was the 4 pairs solution with 8 tests.
In its defence, you have a less than 10% chance of actually needing to do all 8 tests.
This was my exact reaction as well lmao
@@tealkerberus748 I'm pretty sure that on average, you'll find the good batteries faster with the 4 pairs solution, because when you try a pair and it doesn't work, the odds of getting a good pair if you throw both batteries in the "bad" pair away are always higher than if you keep one of the "bad pair" batteries, since you know you're trading a MAXIMUM of 50% good batteries away for a MINIMUM of 50% good batteries (the remaining batteries are either 3 good 3 bad, or 4 good 2 bad).
I expected it was respectable, but not maximal. NOW... Which is most often quickest ("efficient"?)? 3-3-2, but I'm intrigued about comparing 12, 45, then 78, then 23, 31, 56 and 64. Probabilities... grrr... lunch trumps. Anyone? ;)
8 is 1 more than 7, not 1 short of it. checkmate, math nerds
6:48 it's not four more tests, it's just 2 more. You're doing more than you have to.
It is 4, as there are 4 possible size-2 subsets of set {1,2,3,4}, excluding {1,2} and {3,4} as they have already been tested:
{1,3}, {1,4}, {2,3}, and {2,4}
2 tests cannot narrow down which of these will guarantee a success.
@@snowthemegaabsol6819 You're right. Must have been overtired and saw some imaginary logic to it.
This is the best solution and heres why
If there are 4 good batteries, you split them into 3 groups
This means 1 of the groups will always have two batteries
If there are 10 good batteries, you group them into 9 groups (20 batteries total). Thay means one of the groups must have 2 good batteries. The groups would be 3,3,2,2,2,2,2,2,2
A group of 3 batteries has 3 different matches to make and a group of 2 batteries has 1 match (lets call match "m")
3m+3m+1m+1m+1m+1m+1m+1m+1m
13 would be max amount to find 2 good batteries in 10 good and 10 bad batteries
I wrote a script to check which method is fastest on average (out of the 3 good ones), these are the results:
Method 1 - 1 - 15 2 - 14 3 - 13 4 - 12 5 - 4 6 - 4 7 - 4 8 - 4
Method 2 - 1 - 15 2 - 10 3 - 6 4 - 10 5 - 6 6 - 6 7 - 9 8 - 8
Method 3 - 1 - 15 2 - 10 3 - 10 4 - 12 5 - 7 6 - 7 7 - 9
Notation: How many tries are required in how many cases, so 2 -14 means there are 14 configurations that require two tries to solve.
And this is how many tries each method needs on average:
Method 1 AVG - 3.34
Method 2 AVG - 4.08
Method 3 AVG - 3.61
In the final method you should be careful with the order of tests, for the best average speed you should try one pair of the first group of three, then one pair of the second group of three then the last group/pair, then another pair of the first group then another pair of the second group then the remaining two tests; that's one of the good orderings of the tests.
Considering your notation, in order to not confuse the reader, you may replace the first hyphen in each line by a colon. E.G Method 1 : 1-15 2-14 ...
With good ordering of the tests, I found that the third method gives: 1-15 2-14 3-13 4-8 5-7 6-7 7-6
And that makes an average of 3.32857 which outperforms the first method. Please check it to confirm.
@@ahmedouerfelli4709 you are correct. Doing the tests in the order you described does result in better average takes, 3.32 as you said. Which is just a hair better than method one. Nice catch
Nice work!
However, I think there is a mistake in the list of "number of configurations" for Method 2 ; it should be
[15 , 10 , 10 , 6 , 6 , 6 , 9 , 8]
instead of
[15 , 10 , 6 , 10 , 6 , 6 , 9 , 8]
That would lead to an "average" (or expected number of tests) of 4.02857... tests, instead of 4.08 tests.
By the way: the expected number of tests for the 23-tests approach in the video, is... exactly 7 tests!
@@ahmedouerfelli4709 Actually, an even more efficient order for the 7-test method is to start with a pair from each group during the first three tests, then to do the two other tests from one group of three, and end with the two other tests from the other group of three. Or concretely:
(1&2 , 4&5 , 7&8 , 1&3 , 2&3 , 4&6 , 5&6)
This gives the relative frequencies of success per test as
[15, 14, 13, 8, 8, 6, 6]
and hence the average/expected number of tests is 232/70 = 3.31428571...
EDIT: I have just verified that this order is indeed the _most efficient_ order of the seven pairs in the 7-test method, and that the order as presented in the video is the _least efficient_ order of the pairs in the 7-test method (253/70 = 3.61428571... tests).
(If we divide the eight batteries into three groups A, B, and C, with A and B each containing three batteries and group C containing two batteries, then this most efficient order can be represented as ABCAABB ; and the least effiicient order as AAABBBC . There are a total of 70 orders (each with 72 equivalent permutations), but they can be reduced to 21 distinct cases (since for example AABBCAB works out the same as AABBCBA ; or AABACBB works out the same as AACABBB.)
If the seven pairs of the 7-test method are just put in random order, then the expected number of tests is 240/70 = 3.4285714... (which is also the expected number of tests for the order AABCABB ).
Me buying 2 new batteries from the nearby store…
Problem Solved!
Maybe it’s the security person in me, but my first impulse is always to hack the problem instead of doing the math. I appreciate the math, but precision of language is an equal challenge, and is relevant to every word-based problem.
exactly, if half the batch is bad then that means even the good ones are likely unsafe and could leak acid at any time and ruin the components.
@@stm7810could just be a different production line
@@kakuwave Then the answer is eating your boss, actually that's always the answer.no boss means no bad batteries.
Practical real-world solution: You can do it in six tests if you test one at a time. With a bit of wire, you can overcome the flashlight’s design limitation of requiring two batteries, and unless it was a uselessly dim flashlight to start, the bulb should still be visibly alight with half the voltage. Worst case scenario there you hit a good battery and then four bad batteries after which you know which batteries are good and your sixth test lights the flashlight fully.
I knew someone would post this! That is the only solution I kept thinking.
Tell us how to overcome the flashlight's design limitation of requiring 2 batteries. Thanks!
I have an expensive LED flashlight that will flicker if you put in one good battery and a totally dead battery (as measured on voltmeter).
This would only work if the bulb doesn't burn out on 3 good batteries.
Yes but....
7:32 this is the best procedure I could think of within a few minutes of the video pause. Curious to see what the 7 step solution is.
This is very similar to the "fake among eight coins" problem where we need to divide them in a 3-3-2 formation.
I like this 332 solution as it’s a little counter-intuitive to split the batteries into uneven groups… definitely caught me out
i thought about the second method because i simply don't have the braincells for the other cases
Not that difficult. I also gave up only a bit later
My method required 17 tests. You're good.
If anyone is curious, a group of 5 batteries is guaranteed to have at least 1 working battery. Isolate 5 batteries, that leaves 3. Test each of the 5 against the remaining 3. This will take 5×3, or 15 tests. If all 3 fail, the remaining 5 contain only one bad battery. Test any 2 pairs without repeating a battery and success is guaranteed.
My flashlight is actually a Power Bank, that has 2 of 18650 3V batteries. They are connected parallel - yes, they are, not series. Putting two different condition batteries ruins the good one and burns the house. But testing would be easy, one at a time so 2 goodies are found in 4 tests only plus that only-for-this-game rule that you must put the light on in the end even when you know already which are good.
For that I just pull out my old bike lamp and connect that across any given battery.
What if you arrange them in sets of 2 (so you have 4 sets of 2).
Then you try the first set, if it doesn't work you try the second set.
If the second set doesn't work, you change one battery from set 1, with one battery from set 2, and then try set1 and set2 again.
Worst case, these 4 tries don't work.
Then you move on to set 3 and set 4 and do the same.
This should theoretically only take you 6 tries to get to the correct answer.
In the first group (first 2 sets) each set can either have this (W = working, B = broken):
WW
WB
BW
BB
If either set has a WW, then you win in 2 tries, if both sets has a WB or a BW, then you win in 4 tries.
The only situation you don't win in 4 tries, is if the group has WB BB, in which case, it means that the second group (the set 3 and set 4) necessarily has a WW, which can be the second one you try.
So theoretically it should take at most 6 tries to get to a correct pair.
Is there an error here?
K so I found my error, but I'm not going to say what it is, in case somebody wants to try and figure out what I did wrong :)
The error is: Considering the case where each pair contains exactly 1 good battery, in tests 3 and 4 after the swap of two batteries between the first two pairs [WLOG let's say 1 and 3], if they are both good or both bad, it will make no difference.
@@snowthemegaabsol6819 Yes exactly :D
So to fix this, we just do another switch (since we keep track of the batteries) and have 2 more tries, which puts the maximum number of attempts at 8.
I split it into groups of 2 and got a best of 8 tests. Didn't think to try larger groups. Good old dynamic programming always gets me.
my answer was 15 tests, by using the first solution but eliminating redundant tests:
12, 13, 14, 15, 16 (after these tests, it is certain that 1 must be bad)
23, 24, 25, 26 (after these tests, it is certain that 2 must be bad)
34, 35, 36 (after these tests, it is certain that 3 must be bad)
45, 46 (after these tests, it is certain that 4 must be bad, and the other 4 batteries must therefore be good, so one more test is needed)
What happened to your 7th and 8th batteries? 🤔
@@skitzocalypso5840 you never get to them because with the assumption that the tests go as badly as possible you cut out the batteries from 1-4 as 100% bad and 5-8 are good.
The logic for elimination is as follows: I am holding a battery (1) if this battery is good then there are only 4 bad batteries in the pile. If I test it against 5 batteries, I MUST find at least 1 good battery within that 5. If the torch doesn't light even though I'm certain a good battery HAD TO take the second slot next to (1) then I know (1) is bad. Thus you identified a bad battery - now the remaining pile only contains up to 3 bad batteries.
You never need to test 7 and 8 because the objective is to find TWO working batteries so you stop after that happens. 7 and 8 do contribute but only by their properties as being part of this group which must contain 4 bad and 4 good batteries.
@@Qsalis but doesn't that rely on 1-4 being bad? What if the 7 & 8 are bad? And a pair from 1-4 is still good eg 1 & 4?
@@skitzocalypso5840 if a pair from 1-4 is good then you ended the testing early by finding it. you simulate the "worst case scenario" because lucking in and hitting the good ones on the very first try is always a statistical possibility, but has no bearing on what our strategy should be.
it's a process that would end at any point if you have hit 2 good ones, and our goal is to find a solution where no matter how "unlucky" we are with the process, we find the "goal" eventually. And then to refine the solution to find the "goal" faster.
I think a part is missing in the last demonstration, it took me a very long time to understand what they trying to do with the "4 nodes without links between them".
Better than me, because I still can't understand it... and I normally excel at math...
@@ShawnF6FHellcat The first thing is that you stop once you get the light. So there is no decisions to make depending on the result of a test.
You can represent the batteries with nodes, and the tests with edges.
You have 4 good batteries, i.e. 4 good nodes.
To "win", you need to have an edge between 2 of theses 4 nodes. i.e. to have a test with 2 good batteries.
The second thing, is that we assume the worst case.
From a given graph with 8 nodes and X edges, the good batteries can be any combination of 4 nodes among these 8.
This means that, in your graph, if you don't have a node between a group of 4 nodes, this means these 4 nodes form a combination of good node for which you will lose (i.e. it is the worst case).
So we want to prove what with 6 edges, we have a way to link the node in such a way that there is no group of 4 nodes that doesn't have a link between them (i.e. you win in any cases).
This is similar to prove that there is at most 3 nodes that doesn't have a link between them (if you have one more, you have 4).
@@Neckhawker Thanks, I can kinda understand now, but I think it's the terminology that's throwing me off, specifically "node" and "edge". I've seldom if ever heard of "nodes" outside of video game objects and body parts, so I'm a bit confused as to their mathematical meaning. And using "edge" instead of something like "link" or "connector" is strange to me.
@@ShawnF6FHellcat"Edge" is a term inherited from geometry, namely the edges of a polygon.
@@stevenfallinge7149 I don't think we ever used "edge" as a technical term in Geometry, just the dictionary version; but it has been about 8 years since then, so I could be wrong.
I didn't finish the video but this is my take.
50:50 on dead and good battery.
Battery 1 to 8.
Test 12,34,56,78. Probability is quite high for one of those to work.
If all didn't work. That means it's all 1 good + 1 bad battery combo.
Just get 2 random pair and switch their partners.
For example 1234. Just test 13,14 + 23,24.
I came up with 7 tests too. I also fairly easily found that you need at maximum only TWO more tests to find ALL the good batteries (there are two branches to check: if you needed didn't get it in 4 tests or if you did. Both could need 9); so unless you are in a hurry, you really ought to do that too!!
Wait... In the 3-3-2 test, we found at most one good battery in each triplets, in the worst case. So, by elimination the remaining two are good for sure. So the 7th test is not required.
At 1:19 said to include the final test. But otherwise 7'th test wouldn't be needed.
But in the question itself explained that “final test turns the torch on” which means even if there are only 2 good batteries answer is 1 test!
@@HemanthKs-b1r you failed.
There are C(8,4) ways to arrange 4 bad and 4 good batteries in a set of 8. C(8,4) = 70. To write a integer between 1 and 70, 7 bits are needed. Each test provides 1 bit, so we need at least 7 tests. QED
Nice, mathematical proof of theoretical minimum, and the fact that the minimum is in fact possible is great.
If the problem were to identify the status of every one of the 8 batteries, then we would need to distinguish between 8C4=8×7×6×5/(1×2×3×4)=7×6×5/3=7×2×5=70 possibilities. As 2⁶(=64)
How does each test provide 1 bit?
"Each test provides 1 bit" would imply that the outcome of a test would divide the number of still possible distributions by 2 . However, if we'd look at the worst case scenario of the outcome of the first test, it doesn't appear to be true.
A priori, there are (8 choose 4) = 70 possible distributions of four good batteries among 8 batteries. When the first test doesn't result in lighting up the flashlight, there are two possible reasons:
- there is no good battery among the two first-tested batteries. So all four good batteries are among the 6 yet-untested batteries. The number of possible distributions in this case, is (6 choose 4) = 15 .
- there is one good battery and one bad battery among the two first-tested batteries. So there are three good batteries among the 6 yet-untested batteries. The number of possible distributions in this case, is (2 choose 1) * (6 choose 3) = 2 * 20 = 40 .
So the number of still possible distributions of the four good batteries among the eight batteries after the unsuccessful first test, is 15 + 40 = 55 . The number before this test was 70 ; from 70 to 55 , that's hardly a division by 2 (or a gaining of 1 bit of information).
(If we have performed the second test, then in the worst case scenario, there are still at least 41 possible distributions, which is more than the "remaining" 5 bits could represent since 2^5 is only 32 ; so how would two tests mean that we've gained two bits of information?)
@@yurenchu I guess each test provides _at most_ one bit. Never more.
@@paulstelian97 Well, that's not true either. Look at the second 8-tests method in the video (between 7:47 and 10:47 ).
After the 6th test fails, there are still 17 possible distributions of the four good batteries:
- {1, 2, 3, 4} are all bad, {5, 6, 7, 8} are all good : 1 distribution
- {1, 2, 3, 4} are three bad batteries and one good battery, {5, 6, 7, 8} are one bad battery and three good batteries: 4*4 = 16 distributions.
At the 7th test, a pair from {5, 6, 7, 8} (let's say (5&6)) is tested. After that test fails, there are 8 possible distributions left:
- {1, 2, 3, 4} are three bad batteries and one good battery, {5, 6} is one bad battery and one good battery : 4*2 = 8 possible distributions.
So the 7th (failed) test decreased the number of remaining possibilities by a factor greater than 2 (namely, from 17 to 8 )! Or according to the terminology of your/the original commenter's reasoning: the 7th test provided more than 1 bit of information.
It appears there is _no basis at all_ to claim that "each test provides (at least/at most/whatever) 1 bit of information".
I always wonder if we can do this kind of problems using Shannon’s theory of info. We start with entropy of C(8,4) and need it to be lower than C(6,2), each experiment would lower the entropy by 1/4 (excluding the case that they both work) etc.
For sure there are links to Information Theory, but using it directly may not be feasible. For example each experiment will give you some amount of information (let's say b bits of info), but will 2 experiments give you 2b bits of information? Nope, they will give you at most 2b bits of info. If you are lucky you may use Shannon theory to prove 6 experiments won't be enough though.
Let a good battery be 1, bad 0. The arrangements of good / bad batteries are "bytes". The number of eligible arrangements is the number of bytes with 4 bits set. This little script does the job of counting them:
```
fourbit = 0
for i in range(256):
if i.bit_count() == 4:
fourbit += 1
print(fourbit)
```
Turns out, they are 70. Now, 2^6=64, not enough to distinguish between 70 things, but 7 bits are enough. I had figured that 7 is the optimal solution, but I couldn’t find anything better than 8, so pressed play to get the answer.
@@OrangiaNebula If you had to identify all 4 good (or all 4 bad) batteries, then, yes, you would have C(8,4)=70 cases to distinguish, and it would take at least 7 tests to guarantee solving it, no matter what binary tests you have available.
However, you only need to find 2 of the 4 good batteries, so, while you know it can't be harder to solve than identifying all 4, it's possible it could be easier. For example, if you already have a battery you know is good, so you're actually testing just one battery at a time, it would only take at most 5 tests to identify 2 good batteries (if only 1 of the 5 is good, then the untested batteries are all good), while it would take up to 7 tests to identify all the batteries. Note that in both scenarios, you'd potentially need an extra step to load the torch with two good batteries.
I came really close to finding the optimal solution on my own! I figured that if you take a group of 6, then there’s guaranteed at least 2 good batteries among them. I split the 6 into 2 groups of 3 and test those trios. if those all fail then I know there’s 1 good battery in each trio. where I biffed it was in trying to find those 2 good batteries instead of realizing what that implied about the 2 I had not used previously 😅
1 "test"
Drop each battery on the table. The four that bounce highest are dead.
i was looking for this one
Seven tests are required to 100% get the lowest number of tests all the time BUT it doesn’t account for the random possibility that the first test gets 2 working batteries.
what it accounts for is the question saying worst case… good job doing an internet buddy
But the job description said no math required?!?
4:28 It's 11 tests, not 23.
You don't have to test each battery against *all* of the remaining ones, you only need to test the first 5 against each other.
Worst case scenario, this group contains at most 1 good battery, so if all tests fail, 6-7-8 are definitely good.
Pick any 2 of them for the final confirmation test & you're done.
Actually, _16_ of the 23 tests in the 23-test method can be skipped. So the actual answer is 7 tests.
@@yurenchu
Which 7 tests would that be?
@@KatorNia There are several possibilities. The 23-test Method (in the presented order in the video) is:
*12* 13 14 15 16 17 *18* ,
23 24 25 26 27 *28* ,
*34* 35 36 *37* 38 ,
45 46 *47* 48 ,
*56*
From these 23 tests, we could skip the 16 non-bold tests, and only perform
*12* , *18* , *28* , *34* , *37* , *47* , *56* .
But
*14* , *18* , *23* , *27* , *37* , *48* , *56*
also works.
Sure, except you failed to understand the reasoning this was even explained in the first place.
This is the brain dead option in which you just brute force without care to test every possible combination. It’s what a child could think of but at least it’s an answer.
@@CrypticCobra
That's an artificially created "bad" method.
I mean, with that reasoning you may as well test 1-2 & then 2-1, 1-3 & 3-1 etc, to create 46 unnecessary tests instead of 23.
I thought we were talking math, where you don't prove the efficiency of a method by intentionally misrepresenting the efficiency of another.
_My comment stands._
Found 8 tests at worst, 1 at best before clicking on the thumbnail. Now I'm writing it down before watching.
As a developer, I loled with the first solution, if it was someone I was interviewing I would be just like: "thank you and good luck dude".
The obvious rapid solution for me was the second one.
The answer is 6. You only need 6 tests to be sure that you have 2 good batteries in the flashlight. You said it yourself at 12:14 ! That 7th one is unnecessary, it’s not a “test”, you’re already mathematically positive they work.
The intro said that you must include inserting two good batteries at the end as a test
On my own, I would've solved this in a simpler fashion. I would've done 4 pairs, 1-2, 3-4, 5-6, 7-8. I now know that in each pair there is a good battery, and a bad battery. I can disregard 5 through 8 because I know there's at least two good batteries in 1 through 4. I then would test 1-3, and 1-4. I then test 2-3, and if it's still off, I know that 2-4 is my good pair of batteries.
Wonder how the proof is right if the approach you describe shows you can turn on the lamp on the 6th test. Maybe the proof is for identifying all 4 good batteries?
@@jfmrod I still got 7 tests with my method though. I needed to test 2 with 3 or 4 for the last test to guarantee I found my pair of good batteries.
You didn't listen to the question properly. Haha. It said to include the final test of inserting 2 good batteries.
This was my solution as well.
I think we can optimize however. After 12 34 56 we know either 78 is good *or* each pair of batteries has 1 good battery. So 1278 is guaranteed to have 2 good batteries. (3+5 tests bah)
What more, 12 34 failed means at most 2 good: so 5678 is guaranteed to have at least 2 good. (2+6 tests bah)
12 23 13 failed means 45678 has at least 3 good. 45 56 46 failed means 78 has at least 2 good. Which ends up with OP's solution.
12 23 34 13 24 14 failed means 5678 has at least 3 good. 56 78 solves it at 6+2=8 samples.
12 23 13 means 45678 has at least 3 good. 45 67 means 8 is good. 48 58 wins. 7 steps, and not the 3 3 2 pigeonhole solution.
@@adamnevraumont4027 Your last 7-step solution is equivalent to the 3 3 2 solution. The first triple is 1-2-3, the second triple is 4-5-8, and the pair is 6-7. You perform the tests in a different order, though, and you used a different way to arrive at the same set of tests. Actually, that's not surprising, as it is likely that all 7-step solutions are equivalent. Anyone cares to prove or disprove that?
Tongue the batteries, no need to use a flashlight to see which one works.
Or if it is not a 9volt, you can drop them and the used ones will bounce more.
@@Aluzky.Irezumi i was thinking this too, but might fall under circumventing the riddle.
To be fair, though, i'd tell them they should hire me for my expertise since I seem to know more than them.
You do still end up with 8 tests if you have to lick all of them. Your test is fastest if that's what counts for the riddle. You'd have to hit 4 good batteries along the way and can stop there to match or beat this video's solution.
@@technocolossus dropping in 3s would be considered one test. The drop test is relative to the other batteries. And you'd really only need 2 drops. You could do 4 at a time, but you might not be able to track them all at once
@@technocolossus 5 at most actually. You need to find only two good batteries, even if you get 4 malfunctions in a row, next two are supposed to work.
If you get 3 bad batteries and one working, then fifth test will either result in you finding good battery making a good pair or you finding the last broken one, guaranteeing that you can pick any of the last three
But which test finds a solution in the lowest number of tests on average, given random distribution of bad batteries?
I had originally through bad meant the voltage was just low so the pair of 1 good 1 bad wouldn't be enough to use the flashlight but still distinguishable from the pair of 2 bad (i.e. the filament would glow a little). I got to 5 with that assumption but I wonder if there's some clever way to get to 4.
Being a bit pedantic, @11:55, the descriptor for 456 should be "exactly one good and 2 bad" since the 123 tests reveal that one of the 456 batteries must be good (and also now know that one of the 123 batteries must be good)
very good spot 👍
Can you rephrase that?
@@jaideepshekhar4621 he meant that instead of an uncertain, "at least," the video could just have stated the exact numbers, since that's a given at this point.
Here's how I would answer this on a job interview: Bounce them.
Drop AA batteries from a decent height and, although I forget if the charged ones bounce and the discharged ones don't or if it's the other way around, you will still be able to separate them into two distinct groups of 4. Then you pick a group at random, and with a single test you'll know if that group is charged or not. You will have then identified not only two working batteries, but all 4 of them in a single test.
That's good domain knowledge, but the bounce test can only consistently tell the difference between totally new batteries and batteries that have been used at all. A battery at 99% charge will bounce similarly to one at 50% charge or 0% charge.
True this
My naive approach is as follows. Split the batteries into two piles of four batteries each, and then test each pair in the first pile (6 tests maximum - 12, 13, 14, 23, 24, 34). Either you find a good pair (you're done) or you don't.
If you don't, then we know the first pile contains either only one good battery, or no good batteries. So in the worst case, the second pile contains one bad battery. We can then do one test on pile two, testing 5 and 6 together (test 7). If it does not turn on, we know either 5 or 6 was bad. Therefore, batteries 7 and 8 MUST be good. (test 8)
So in my naive approach, 8 tests is worst case. Edit: Oh, turns out that was strategy 2! I feel smart now
You don’t need to do the last test since you already know via process of elimination so it’s 7 😊 By extension of this logic you can actually generalize the answer to n/2+3 tests for n batteries where n is even and half are bad
I think I have a solution in six tests. Consider we select four batteries. If more than one of them is good, then we will need no more than four tests to find the pair (eg 1,2 are good, then 13 and 24 fail, 34 fails but 12 good and we can stop looking). Therefore, if we are still failing after 4 checks, we now know our selection is 1 good and 3 bad or all 4 bad, and thus the remaining unselected batteries must have at lest three good batteries among them. It will require no more than 2 tests to find a good pair. 4 + 2 = 6. QED.
1&3 , 2&4 , 3&4 , and 1&2 could also all fail when {1,4} are two good batteries, or when {2,3} are two good batteries. So no, it's not guaranteed that after the first four tests fail, there would be at least three good batteries among the remaining untested four batteries.
@@yurenchu I see it now. Thanks.
@@WunUnknownPlayer You're welcome!
7:25 dont we need to do more tests to find out which 2 good batteries are in 5 6 7 and 8? It took 8 tests to find 2 batteries 2 and 4
12:47 wouldnt we still need to figure which 2 batteries are good out of the 2 pairs of 3?
The stated goal was to find (and test) any pair of good batteries, not to identify all four good batteries.
@Ardub23 ahh thank you! Missed that part!
As the last pair of cells in all the solutions you provided need not to be tested, as it is a certain event that the last pair will light the torch for sure.Thus the minimum no of attempts will be '6'.
Sure, but that's why he said "for the purpose of this puzzle, include placing two good batteries into the flashlight."
So in a sense, he turned the puzzle into _"how many replacements are needed before the flashlight can turn on"_ not _"how many tests are needed to find 2 good batteries."_ Same results tho, you just add 1 to every solution.
You have to do the final test to know for certain that the flashlight works. If the flashlight is broken then you haven't actually been testing the batteries, you've been demonstrating that a broken flashlight doesn't work whether it has good batteries or not.
I got asked this once in an interview, after the engineer noticed that I used to run an instrument shop. I told him 1, just needed some resistors and some wire or foil. He called me a liar and ended the interview shortly after. Never asked me how, just bounced me.
Five years later he found me on LinkedIn and apologized. It took him that long to realize what I was getting at, and to also summon the courage to talk to me again. He even tried it himself by getting some faulty batteries. Done in one. He promised to buy me a beer, but I was kind of hoping he would refer me to a job. Still aint got that beer.
I'm... so sorry to hear that..
If you're really still looking for a referral, I can help get you one
You should send him a flashlight as a gift with 2 good batteries and the rest bad.:)
You obviously did not understand the question and fail miserably. The whole point of the question is to work within the rules presented.
Nice fake story, bro.
Yea just give me a paperclip, or just check if they bounce
In real life the flashlight would glow dim with 1 bad & 1 good battery, letting you know that you have a good one, split them into 2 separate piles and then test another pair, if it also glows dim, then leave one and take one from the previous piles, either it will not turn on (swap for the other two), glow dim (swap for the opposite pile) or turn on fully = 3 tests, realistically.
I wonder, is there a general formula to figure out the minimum number of tries to guarantee a working pair?
To be precise, is there a formula that will work with any given value for the following variables: nrGoodBatteries, nrBadBatteries, nrNeededBatteriesInFlashlight
In the video's example, we're working with nrGoodBatteries=4, nrBadBatteries=4, nrNeededBatteriesInFlashlight=2
Is there a formula that gives us the minimum with, say, 4, 10, 3? Or 12,5,4? Or any arbitrary number for these variables?
"I test 1+2, 3+4, 5+6, 7+8, 1+3 and 1+4 and I'm 93.6% sure. This solution is only mildly significant (p=0.064), exactly like the job you're hiring me for, and that's why I'm the perfect fit"
How in the heck would a scenario emerge where you know for certain there were exactly four bad cells of a batch of eight, but not know which *any of them were in the first place?
A careless person just replaced batteries for his two flashlights, and left the 4 discharged batteries with the remaining 4 good batteries in the drawer.
@@yurenchu "Careless person" a.k.a. I bet most of us have done that at some point
@@Cowtymsmiesznego that's why I've been exclusively using rechargables for the last 20 years. There are no "bad" batteries in my home. If they're too low to run electronics, they get recharged.
The complexity of the solutions that people have come up with show that this fails as an "interview question": it is unreasonable to expect someone to come up with such a solution from scratch. It is more a puzzle which someone might decide to tackle if they're interested, and might spend many hours on before coming up with something that looks like a solution.
@@rosiefay7283 i came up with a not optimal, but pretty good approach (8 checks worst case) in like 2 minutes from just thinking about the problem. maybe i just got lucky timewise but the parts of the problem space I focused on (i.e which possible permutations exist) led me directly to that approach. that's probably what's being looked for in an interview type of context rather than coming up with the exact optimal solution because you've seen it before -- that's why tech companies' interview questions are always being switched out for new ones
Interview questions aren't about the answer though, more about the problem solving ability of the candidate. The question needs to be worded in a way to encourage that process to be shown, however.
Nope, I figured it out in about 15 seconds. Actually guesstimated it in 4 seconds and took the other 11 to mentally prove it. Coming up with it "from scratch" is exactly the point, that you won't always have someone holding your hand in life, that you need to be able to handle some situations from scratch.
Tests like these separate those good at math puzzles from those that aren't, which is the point. If it takes you an hour, your puzzle solving skills OF THIS TYPE are inferior to those who can do it faster, for the employer to find people who are adept at puzzles like that, or else choose a different kind of problem to solve that is more relevant to the employment position, and again, someone not good at that type of problem solving, will take a lot longer than someone who is.
Besides as the video stated, some employers won't even care if you reach the most optimal solution, just that you reach one that works. Anyone can do that in a few minutes even if they aren't good at verbally describing it or drawing pictures about it.
The presented solution is incorrect. And I demonstrated how to do it in 6 tests in a couple of minutes.
The second approach is 7 tests because you don’t need to check 2, 4. You already know 100% that they are both good.
yes but you don't identify the other 2 good batteries
@@magicphred The question isn't to identify all 4 good batteries, it's to identify just 2.
It is stipulated that "testing" the final two batteries that you know are good counts. In a worst case scenario, the last combination you plan to test will be the good one.
This is why at 1:20 he specifically says to include the final insertion of two good batteries in the tally. It really doesn't change the puzzle, it just means all solutions would be 1 test fewer. But that's also a nonsensical thing to do, because the goal isn't to find the good batteries it's to turn on the flashlight.
in practice a flashlight will usually produce a dim light with one good and one dead battery. find a pair that doesn't light up at all, then use one of the two confirmed bad ones with the rest in order to find the all of the singles that produce a dim light which you would know are good. then you find all of the good batteries.
I assume the flashlight has some electronics that only run at above 1.8V (0.9V is the regular cutoff voltage for testing regular 1.5V alkaline batteries)
The 7 test solution is amazing! Great puzzle, I've come to the first 8 test solution anyway
That 7 test is really only 6 in that solution since you dont really need to test the last 2
THANK YOU! Yes, it is impossible for the last two not to be good based on the facts provided. It is a 6 test optimal solution.
I just commented this and was looking for this comment as well. 6 is the answer.
No one asked the obvious question: "How did you know that 4 batteries are bad"?
You start off with two containers next to each other. One with fresh batteries, the other with used batteries you know died. Someone knocks over both containers mixing the good and bad batteries with each other
He said you got the good and bad ones mixed up
@@ashton046 How did he know without having them tested in the first place ?
Average manufacturing defect rate from that one factory
If you're running from the zombies, you don't need to do the final test. So, you do 6 tests and run out with the last two batteries if all 6 failed with confidence that the last two are good.
Or just take all 8 batteries and run to a safe spot. If you can run in the dark eh? You will put in the last 'test' because you need the flashlight on, of you're not in that much of a hurry in the first place.
You are of course right that we can conclude it after 6 tests, but that is why it was stated in the intro that the last test counts as 1.
Idk if I’m just avoiding unnecessary number pairing or not, but I’d just drop the batteries a foot above a hard surface. If it bounces an inch or more it’s empty.
The last solution is cool, it's so deceptively simple. I love how because the worst case is assumed, it basically forces the last pair to be good. Even before the 7th test you know it will work. I wonder if the optimal number of tests in the worst case for any even set of n batteries where half are good and half are bad is always n-1. I'm not smart enough to prove this but it sounds right haha.
0:40 "If you have one good battery and one bad battery, the flashlight will not work." That's not how batteries nor flashlights nor electricity works. The simplest, easiest solution is to go buy a dirt cheap battery tester for a couple bucks and then test all of the batteries individually. Or get a slightly more expensive multimeter for $30, which has lots of additional uses outside of battery testing. Now the worst case is that you only need to test ZERO times to "find" all of the dead batteries using the flashlight because you are using the right tool for the job. Thus, the correct answer is ZERO. Use the correct tool for the job and stop asking terrible questions like these in interviews.
Also, if these are 9 volt batteries, you can use your tongue instead. Just touch each battery to your tongue and if you get a strong shock, then it's probably a good battery. If you get little to no shock, then it's bad. Again, no need to use the flashlight at all and thus you've conducted ZERO tests with the flashlight.
Also, there is no such thing as a dead battery. It just might not be storing as much of a charge as you would like it to be storing. This is a bad question because anyone remotely familiar with electronics is going to tear this problem apart for being extremely vague on the specifics.
Depending on the battery and the flashlight, it is possible for it to not glow enough to be seen at 1 good 1 bad. And, the bad battering could be insulators for all we know. Don't apply physics to a reasoning question
@@privacyvalued4134 you sound like the kind of guy who would ask why you’d build a puzzle when the picture is already on the box.
There is nothing terrible about this interview question and it's actually quite interesting imo. It shows problem solving in a hypothetical situation which has value.
The question said "in the worst case". Then the answer is 19.
Loads of errors here. Like 10:35 - no you need 9 tests. You will not know which single of the batteries are bad. You need to test the failed pair against the good pair to single out the bad one.
No, you don’t need the info which of the 4 remaining batteries the bad one is. You know from the previous testing of the first group of 4 that exactly one of the second group of 4 is bad. When you test the first pair of the second group of 4 and the flashlight is off you know that the other pair of the second group of 4 definitely consists of two good batteries. You test the other pair and you know the flashlight is on hence these are two good ones. The problem is solved. It is true that you don’t know which of the first pair of the second group of 4 is bad, but you don’t need to know you already have two good ones.
You've failed the actual test. It's a parsing requirements test. You were asked to find 2 good batteries, not isolate all 4 good batteries.
And this is why you always read the question in full before giving an answer; so that you don't leave silly incorrect comments on videos like this.
i was doing the dishes while watching the video and also missed the part where they only want 2 good batteries 😅
Confidently incorrect.
Easy. You tap the batteries on the table, letting them go free when they strike. The ones that bounce are bad, the ones that fall flat are good.
Actually, you can also slightly alter the method of pairs for a maximum of 7 tests. These are the batteries you need to test: 12, 34, 56, 71, 72, 83, 84 (there are other combinations, this is just one of them)
It works because after testing the first 3 pairs together and the flashlight being off, you don’t need to test the last pair to know that there’s at least one good battery in it. It’s either a good and a bad one or two good ones
Then, choose one of the batteries of the last pair (7 or 8) and test it with another pair (12, 34 or 56). If the flashlight is still off, choose the remaining battery (7 or 8) and test it against a different pair (it’s important that it’s different)
If 7 and 8 were a mixed pair, it works as explained in the video. If 7 and 8 were both good batteries, you choose either one and test it against a pair and if the light isn’t on yet it’s because you accidentally chose the pair with two bad batteries. Just switch batteries (it doesn’t matter cause they’re both good) and test it against a different pair, which will contain a good battery
That’s the solution I found. More complicated to explain but pretty simple all things considered. And it will take slightly less attempts on average compared to the method explained in the video
It is the same seven test pairs as in the 7-test procedure in the video, but in a different order (and labeled differently). But indeed, your order is the most efficient order of the 7 pairs, while the video's order is the least efficient order of the 7 pairs. (Less efficient than the presented 8-test solution, even.)
Okay, but you can not know if the torch is working correctly... :D
These brain teasers are about as useful as a personality test for seeing if someone is fit for a job.
So depending on which job and which test, pretty useful then? If I'm trying to land a probe on mars, I kinda want someone who can solve a brain teaser for maximum efficiency while leaving 0 room for error. If I'm trying to get funding to build my mars probe, I kinda want someone who's at least self aware enough to put the 'correct' answers on a personality test
@@-maxx- You are assuming those test map accurately to real life situations.
@@alejandrocambraherrera8242 not necessarily, but I am assuming they map more accurately than random samples
You say that now... better hope you don't get squid gamed
The tests don’t need to map, just the problem-solving toolset. In fact the tests SHOULDN’T map, because then it’s something that should be part of the training because it’s a solved problem
So... the 7 test method is wrong. Because if you can confirm 1 good battery between 3 batteries, twice, you then have to figure out which of those 3 is good.
Test one group of three: AB, BC and AC
Test a different group of three: DE, EF and DF
No need to test the remaining batteries. If neither group of three has two working batteries, you know the extra pair is working.
If any pair within a group of three worked, you found a working pair.
Do one final test with two batteries that have been shown to be good.