Could you pass this interview? The famous batteries and flashlight logic puzzle

[@doq]

If your battery supplier has a defect rate of 50% you might want to consider a different supplier. 7 worst case btw.

[@tigerboy4705]

Gow do you get 7? Max 5

[@myster4775]

​@@tigerboy4705So how did you get 5?

[@tigerboy4705]

@myster4775 by commenzing way too early and missunderstanding the puzzle xD (didn't get that the flashlight needs 2 batteries xd)

[@mr.cauliflower3536]

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.

[@Mephistahpheles]

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.

[@kbsanders]

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.

[@ralfbauerfeind8236]

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]

Wait, there’s dates on your batteries? All mine say is “ _D __-o-__ _*_n_** t* -R- _3 _*_C_** h* a -r- _ge_ “

[@ralfbauerfeind8236]

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

[@mydkarthikmecharena9010]

😂

[@homemade.bits.0]

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.

[@commontater652]

If my boss won't let me use my multi-meter I need a new job.

[@useruser400]

You need a new boss!!!

[@AndreasDelleske]

Solution: Replace boss.

[@eman2867]

New problem: There was a mixup at the multimeter factory and your multimeter came with 8 batteries...

[@JMMC1005]

​@@eman2867 And half of the probes have a broken wire inside.

[@commontater652]

@@eman2867 Well played!

[@SS-YTChannel]

Zero tests needed. Throw away all 8 batteries and get four new ones bc an engineer's time is worth more than four batteries.

[@robcoop6521]

You mean safely dispose of those batteries.

[@SS-YTChannel]

@@robcoop6521 I didn't say throw them away in an unsafe manner.

[@ScottHess]

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.

[@galfisk]

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*

[@StanleyPinchak]

​@@galfiskCFS

[@gonecoastal4]

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.

[@dirkbester9050]

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.

[@gonecoastal4]

@@dirkbester9050 which is why I carry one everyday.

[@threeMetreJim]

And that is why governments overspend.

[@ttmfndng201]

aaaaaaaand... you've failed the job interview

[@rmsgrey]

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.

[@Parlik]

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.

[@douglaswolfen7820]

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

[@douglaswolfen7820]

(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]

still needed to test the 7 and 8 because there is still a probability 7 and 8 are both good batteries

[@allanjmcpherson]

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

[@wizzszz]

Came here to post that. The other test rounds can be shortened by 2 as well.

[@kbsanders]

Plot Twist: The bulb is burnt out.

[@ptorq]

That's why you need the final test to prove that you've actually been testing the batteries, not the flashlight.

[@Fantastic_Mr_Fox]

what if all batteries were bad? You could theoretically never know.

[@josephrissler9847]

Polarity diagram on the flashlight is backwards.

[@bothieGMX]

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.

[@kenmore01]

By the time you figured that out, you had been fired.

[@Byrnage]

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.

[@sheikyerbouty2926]

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

[@lightspeedlagu]

Great observation! To be fair, 23 is correct for an upper bound. But then so is 100!

[@jerkison]

Yeah but 100! is a little too high to be useful, right?

[@lightspeedlagu]

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

[@PhildiusX]

in 16 test you find all 4 good batteries.

[@MisterVercetti]

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.

[@marcvanwesten2759]

Exactly what I thought

[@gljames24]

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.

[@yurenchu]

None of the presented methods in the video always eliminates half at each test.

[@mickyderheld]

missed the opportunity to call half of them baderies

[@rickkwitkoski1976]

or half of them gooderies!

[@samuelcrandall1180]

It sounds a bit too similar to the way "batteries" is usually pronounced to differentiate.

[@bignumbers]

He's an American, so "batteries" is always going to sound like "badderies"

[@LoneBeastYT]

Joke so bad I think you committed "assault" and "badery"

[@PWALYM]

i am sure you will be a good Dad hahaha XD nice dad jokes there :3

[@howareyou4400]

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.

[@ericstelzman5190]

This was on TED-ED. In case you're wondering which video, it's the Giant Iron Riddle.

[@Blade.5786]

Oh THAT'S why this reminded me of the sock pair riddle.

[@TheDarkNerd]

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.

[@arolimarcellinus8541]

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

[@Stratelier]

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

[@Woztek10]

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

[@douglaswolfen7820]

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

[@irrichman]

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

[@chixenlegjo]

This is actually the same tests as the video’s solution. Your groups are just 123 and 678, rather than 123 and 456.

[@황제욱-y1s]

Perhaps it's even better because the average value is lower

[@toastedjam1470]

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.

[@ReallyAmateurPianist]

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

[@nixhalla3uk27]

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

[@bok4822]

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

[@agingerredhead9380]

ah comp sci vs math, get it done or get it done while writing a paper

[@gowzahr]

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

[@kenfrank2730]

During the test say, I'll google that for you.

[@stm7810]

already have a light and I don't buy dodgy batteries since I'm not useless.

[@Lord_zeel]

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 😉

[@SuperS05]

​@@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.

[@FirstLast-gw5mg]

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.

[@shanehebert396]

Try dropping the batteries and seeing if they bounce ;)

[@huzefa6421]

Science over Math 😂😂😂

[@verkuilb]

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

[@scottdobson1276]

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.

[@HxTurtle]

I know what you mean, but he kinda thought about this and ruled it out at 0:24 from this imaginary thought experiment.

[@WowOafus]

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

[@inplfw]

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.

[@inplfw]

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

[@JMacSD]

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.

[@ilnezija]

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

[@inplfw]

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.

[@cguy96]

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!

[@ethanchapman1776]

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.

[@yurenchu]

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.

[@bernym4047]

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.

[@Cowtymsmiesznego]

Apart from it's not the minimum

[@matthewwalker4931]

Split in two groups one 3 and one 5 and see how many test you need.

[@PsychicCellphone]

Solution: lick finger, hold onto negative terminal, lick positive terminal... if you can feel tingle, it's a good Battery.

[@mr.cauliflower3536]

actually, it's still bad, just good enough to tingle.

[@ralfbauerfeind8236]

​@@mr.cauliflower3536Also, 1.5V might be a little too low for you to "taste" the energy. 🤔

[@kenfrank2730]

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

[@PhoenixNL72-DEGA-]

@@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)

[@user-iw6im]

​@PhoenixNL72-DEGA- Same here, it works.

[@verkuilb]

Duracell gonna sue for using their trademarked color scheme and saying half their batteries are bad. 😂

[@XtreeM_FaiL]

Half of the Duracell's batteries are not bad!

[@matthewcodd2939]

This is extremely unlikely to be found infringing, at least because Presh is not advertising any batteries for sale.

[@TexasEngineer]

Duracell leak. I will not buy them anymore.

[@Robert08010]

Change it to Energizer, then it will be true! LOL.

[@Nupetiet]

They aren't dead, they're leaky! Get it right!

[@maartendegroot98]

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.

[@siddharthannandhakumar6187]

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.

[@MinePossu]

At 1:19 said to include the final test. But otherwise 7'th test wouldn't be needed.

[@HemanthKs-b1r]

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!

[@HansLemurson]

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_

[@asin_5]

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.

[@peter_castle]

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]

I'm too old to understand what the meaning of edge is

[@binsarm9026]

@@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

[@physicssquirrel]

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.

[@rmsgrey]

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

[@klchu]

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.

[@Fossil_Frank]

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

[@Lord_zeel]

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

[@Fossil_Frank]

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

[@fdsaa]

@@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

[@michelcolman314]

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.

[@ahmedouerfelli4709]

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.

[@Konstamonsta]

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

[@tyranmcgrathmnkklkl]

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

[@threemar3]

Isn't that assuming battery 1 is good?

[@olafbaeyens8955]

No one asked the obvious question: "How did you know that 4 batteries are bad"?

[@emberguard5009]

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

[@ashton046]

He said you got the good and bad ones mixed up

[@esunisen3862]

@@ashton046 How did he know without having them tested in the first place ?

[@majesticsnowleopard]

Average manufacturing defect rate from that one factory

[@EmperorZ19]

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

[@tealkerberus748]

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.

[@rafetizer]

This was my exact reaction as well lmao

[@CaptainFalcoyd]

@@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).

[@arkaig1]

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? ;)

[@lawrenceredmacher4382]

8 is 1 more than 7, not 1 short of it. checkmate, math nerds

[@empmachine]

This was a really cool one!! Thanks a bunch for sharing!!

[@pannwes]

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

[@ahmedouerfelli4709]

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

[@ahmedouerfelli4709]

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.

[@pannwes]

@@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

[@yurenchu]

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!

[@yurenchu]

​​​​@@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 ).

[@carlpierce2486]

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 ?

[@verkuilb]

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?

[@josefuher6117]

In the case of (B+1)*M =

[@JLvatron]

Try 'F' for Fail!

[@jimi02468]

What about X working batteries, Y broken batteries and Z places for a batteries in the flashlight?

[@stevenfallinge7149]

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.

[@Stefan-xm9qb]

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!

[@Aluzky.Irezumi]

Tongue the batteries, no need to use a flashlight to see which one works.

[@Aluzky.Irezumi]

Or if it is not a 9volt, you can drop them and the used ones will bounce more.

[@josephwilliams1915]

​@@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.

[@technocolossus]

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.

[@josephwilliams1915]

@@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

[@altybro228]

@@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

[@johnywuijts917]

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]

What happened to your 7th and 8th batteries? 🤔

[@Qsalis]

@@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]

@@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?

[@Qsalis]

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

[@Qsalis]

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.

[@wyldanimal2]

7 is the Maximum number of tests that would have to be optimally Done, 1 test would be the minimum, as you might get lucky and put 2 good batteries in during the 1st test. The Square root of the total number of Items, rounded up to the nearest whole number = (group size to test ) , Times the Number of Sought after Items ( 2 good in this case ) Plus 1 Square root of 8 = 2.82 round up to 3, this is the size of the groups to test against each other. so two groups of 3 and a remaining group of 2 Seeking to find 2 good Items, so we take the group size and multiply by the number of items to find, = 3 x 2 = 6, then add the final test, and the optimal results is 6 plus 1 = 7 test.

[@KiraAkaike]

i thought about the second method because i simply don't have the braincells for the other cases

[@3057luis]

Not that difficult. I also gave up only a bit later

[@davileite780]

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.

[@yurenchu]

*A solution for the generalized case:* Suppose there are G good batteries and B bad batteries, and G≥2 ; and the flashlight takes 2 batteries and only works if both inserted batteries are good. If 0 ≤ B < (G -1) , then we can produce a working flashlight in at most (B+1) tries. If (G-1) ≤ B , then we can produce a working flashlight in at most (k*N - (G-1)*T(k)) tries, where N := B+G , k := floor((N-1)/(G-1)) , and T(k) := k(k+1)/2 is the k'th triangular number . *The procedure:* First try (G-1) non-overlapping pairs. That's at most (G-1) tests. Then use the next (at most) (G-1) untested batteries to "complete triangles" with (at most) (G-1) tested pairs (each untested battery with a different tested pair). This takes 2 tests per triangle, so (at most) 2*(G-1) tests in addition, or 3*(G-1) tests in total. Then use the next (at most) (G-1) untested batteries to "complete crossed squares" with (at most) (G-1) tested triangles (each untested battery with a different tested triangle). This takes 3 tests per crossed square, so (at most) 3*(G-1) tests in addition, or 6*(G-1) tests in total. Then use the next (at most) (G-1) untested batteries to "complete crossed pentagons" with (at most) (G-1) tested squares (each untested battery with a different tested square). This takes 4 tests per crossed pentagon, so (at most) 4*(G-1) tests in addition, or 10*(G-1) tests in total. Then use the next (at most) (G-1) untested batteries to "complete crossed hexagons" with (at most) (G-1) tested pentagons (each untested battery with a different tested pentagon). This takes 5 tests per crossed hexagon, so (at most) 4*(G-1) tests in addition, or 15*(G-1) tests in total. And so on. - - - *Note:* I've just figured out this solution by myself. I'm pretty certain that it works (however, if there are any mistakes, please let me know), but I don't know if this procedure is "optimal" (whether "optimal" in the sense of "least number of tests in the worst-case scenario", or "optimal" in the sense of "least number of tests _on average_ "/"least value for the expected number of tests").

[@jonaskoelker]

I was thinking along the same lines, except maybe from a different direction. Here's my loose intuition. If a supermajority of the batteries are good, test them in disjoint pairs. One pair will be good. [I define supermajority to mean G >= B + 2.] Otherwise, perform some tests which moves towards the rest having a supermajority of good batteries. Do these tests as efficiently as possible. Doing all pairs among 3 batteries without light means at least two batteries are dead. Assuming the worst case, that means our three tests have moved the balance among the rest one battery towards supermajority, for a rate of 1/3 (balance-delta per test). [Note: for B=G=4, the specific example in the video, we do two sets of 3 and then the remaining two batteries have a strong supermajority.] If we do all pairs among 4 batteries, that's at least three dead batteries and one good one (balance-delta = 2) in 6 tests (4 choose 2), for a rate of 1/3 again. If we do all pairs among 5 batteries, it's a delta of 3 in 10 tests, for a rate of 3/10 which is less than 1/3. With 6 batteries it's delta=4, tests=15, for a rate of 8/30 which is less than 9/30 = 3/10 which is less than 10/30 = 1/3. And it only gets worse from there. So the plan is: use the supermajority if we have one. Else get there in groups of 3 and 4 if possible. Else, do the smallest number of groups of 5 and then groups of 3 and 4, if sufficient. Else do groups of 6, then 5, then 4 and 3, and so on. I think your solution does the same thing, just backwards. Actually, I can make the thinking one step longer: if _all_ batteries are good (and there are at least two), test an arbitrary pair. Otherwise, if G >= B + 2, move towards all batteries being good by eliminating one bad battery by performing one arbitrary test (and discarding the tested pair if no light). Otherwise [the rest of my argument]. Note that learning one bad battery in a single test is a better learning rate than any of the other options, and the hand-wavy justification for all the other decisions is that we always use the most efficient learning strategy possible given the density of good to bad batteries.

[@DergaZuul]

Graph proof can be done simpler without need of confusing assumptions and contradictions. Just pick vertex with highest degree and remove it with all adjacent edges, repeat it until all edges are gone. Because you remove at least 4 edges in first 2 steps (With visuals this is very easy to see) after that you can only remove 2 more vertices which lead to 4 vertices left with no edges (all 6 are gone) hence 8 vertices with 6 edges always have an independent set of 4 or more.

[@rmsgrey]

Who needs visuals? You have 6 edges, so 12 ends of edges, so the total degree is 12. With only 8 nodes, you need to have at least one node of degree at least 2. If it has degree 4+, then you're removing at least 4 edges in the first step. If it has degree 3, then you still have 3 edges left and your second step has to remove at least one, for a total of at least 4 removed edges in the first two steps. If it has degree 2, then removing it leaves 4 edges, 8 total degree, among 7 nodes, so at least one has degree 2, for a total of 4 removed edges in the first two steps. I will note that if you have a node of degree 6, then you don't remove at least 4 edges in the first 2 steps because you never have a second step...

[@DergaZuul]

@@rmsgrey why would you not have second step? You still can remove node without edges and end up with independent set of six which is more than 4. Of course you don’t need to do second step but it is easier to keep it for consistency and ease of explanation. I think my way of explaining a bit clearer but it is similar in essence.

[@rmsgrey]

@@DergaZuul Because in your definition of the process you said "repeat it until all edges are gone". It's not a serious objection to your argument, just some light-hearted nitpickery.

[@DergaZuul]

@@rmsgrey that is after first two steps, well anyway point is remove at most 4 nodes covering all edges so remaining set is independent set of 4 or more nodes.

[@sunilsharma4659]

Me buying 2 new batteries from the nearby store… Problem Solved!

[@aaronlewicki8000]

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.

[@stm7810]

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.

[@kakuwave]

​@@stm7810could just be a different production line

[@stm7810]

@@kakuwave Then the answer is eating your boss, actually that's always the answer.no boss means no bad batteries.

[@NesrocksGamingVideos]

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.

[@glenk7587]

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.

[@NesrocksGamingVideos]

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.

[@erendorn]

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]

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.

[@erendorn]

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

[@evilkingcaliban]

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.

[@justinmohns8279]

I knew someone would post this! That is the only solution I kept thinking.

[@eclipse-sh1qmZ3mOtcua]

Tell us how to overcome the flashlight's design limitation of requiring 2 batteries. Thanks!

[@JaimeWarlock]

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

[@BartvandenDonk]

This would only work if the bulb doesn't burn out on 3 good batteries.

[@3057luis]

Yes but....

[@markemdee7311]

Without giving it any thought, I came up with 11 tests; so i would have got the job done quicker than most.

[@agoosecalledxaro6679]

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.

[@jfmrod]

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?

[@agoosecalledxaro6679]

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

[@patmenow]

You didn't listen to the question properly. Haha. It said to include the final test of inserting 2 good batteries.

[@adamnevraumont4027]

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.

[@tw11tube]

@@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?

[@Jaszi007]

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.

[@agingerredhead9380]

what it accounts for is the question saying worst case… good job doing an internet buddy

[@samisuomalainen9870]

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.

[@HappyBeezerStudios]

For that I just pull out my old bike lamp and connect that across any given battery.

[@FirstLast-gw5mg]

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.

[@thejaskodoth4630]

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

[@FirstLast-gw5mg]

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

[@ShankarUtthandyV]

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

[@TGNXAR]

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.

[@MephieStopheles]

1 "test" Drop each battery on the table. The four that bounce highest are dead.

[@dee.daithi01]

i was looking for this one

[@MechMK1]

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

[@JB-kv9zk]

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?

[@yurenchu]

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]

@@yurenchu "Careless person" a.k.a. I bet most of us have done that at some point

[@HappyBeezerStudios]

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

[@trevorlebert1929]

Check how they bounce. Dead batteries are lighter and bounce higher

[@dreamsdicc1817]

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

[@veezhang6988]

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.

[@deept3215]

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.

[@OrangiaNebula]

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.

[@rmsgrey]

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

[@okrajoe]

But the job description said no math required?!?

[@MrVirus9898]

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.

[@AyushMo]

I'm... so sorry to hear that.. If you're really still looking for a referral, I can help get you one

[@LiquidAIWater]

You should send him a flashlight as a gift with 2 good batteries and the rest bad.:)

[@stinkycheese804]

You obviously did not understand the question and fail miserably. The whole point of the question is to work within the rules presented.

[@Ohrami]

Nice fake story, bro.

[@catwithoutthehat]

Yea just give me a paperclip, or just check if they bounce

[@meyes1098]

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?

[@meyes1098]

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 :)

[@snowthemegaabsol6819]

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.

[@meyes1098]

​@@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.

[@MrSlerriuqs]

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.

[@thassalantekreskel5742]

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.

[@cajonesalt0191]

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.

[@JLT9150]

True this

[@benoitpoulot-cazajous84]

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

[@paulstelian97]

Nice, mathematical proof of theoretical minimum, and the fact that the minimum is in fact possible is great.

[@MichaelRothwell1]

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)

[@yurenchu]

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]

@@yurenchu I guess each test provides _at most_ one bit. Never more.

[@yurenchu]

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

[@noticespams6540]

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

[@NorthernRealmJackal]

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.

[@ptorq]

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.

[@raj180380]

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

[@hippophile]

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!!

[@andrewhazlewood4569]

The second approach is 7 tests because you don’t need to check 2, 4. You already know 100% that they are both good.

[@magicphred]

yes but you don't identify the other 2 good batteries

[@tobiastames5224]

@@magicphred The question isn't to identify all 4 good batteries, it's to identify just 2.

[@geirmyrvagnes8718]

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.

[@Lord_zeel]

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.

[@Neckhawker]

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]

Better than me, because I still can't understand it... and I normally excel at math...

[@Neckhawker]

@@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).

[@ShawnF6FHellcat]

@@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]

​@@ShawnF6FHellcat"Edge" is a term inherited from geometry, namely the edges of a polygon.

[@ShawnF6FHellcat]

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

[@todaywelearned]

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.

[@bobmartin9918]

It was extemely gratifying to find that strategy 1 was the solution I worked out in my head, although admittedly I only thought of it as it seemed the fastest way to test everything, none of the logical reasoning around the batteries themselves applied.

[@nixhalla3uk27]

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

[@CharlesBallowe]

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.

[@irrichman]

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.

[@rosiefay7283]

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.

[@towaii]

@@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

[@jnawk83]

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.

[@stinkycheese804]

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.

[@udayp]

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)

[@HxTurtle]

very good spot 👍

[@jaideepshekhar4621]

Can you rephrase that?

[@HxTurtle]

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

[@BoxInaCan727]

If you know for a fact there are 4 good and 4 bad batteries you dont need to perform the 7th test, since if the first 6 tests failed you know that the remaining pair consists of two good batteries thus finding the two good batteries with only 6 tests

[@victorvolobuev507]

Indeed, seventh test would verify if your method and logic was sound, and the flashlight would finally turn on in a worst case scenario.

[@snowthemegaabsol6819]

1:18

[@irakyl]

I love puzzles like this 😊 upon seeing the thumbnail I figured out 8 tests, and when you revealed 7 was optimal I paused and found my own solution: 12, 34, 56, 57, 58, 67, 68. Basically just pairwise checking into exhaustive search but I realised you don't need to actually check the last pair

[@totalvoid6234]

That's 8 tests though, all these methods count the final test as one of the tests. Otherwise the tests provided get the solution in 22 , 7, 7 and 6 checks.

[@irakyl]

@@totalvoid6234 The meaning of "don't need to actually check the last pair" is that the sequence can be reduced to: 12 34 56 57 58 67 68 instead of: 12 34 56 78 57 58 67 68 Instead of just assuming I'm skirting the rules maybe try verifying for yourself that the provided info is correct! If you're having trouble it may help to count on your fingers

[@ArticulateArena]

That 7 test is really only 6 in that solution since you dont really need to test the last 2

[@stinkycheese804]

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.

[@phoneoperator]

I just commented this and was looking for this comment as well. 6 is the answer.

[@jwfcp]

Faulty premise, how do you know there are only 4? The goal would be to eliminate all defective inventory, you bring a known good battery and test it against each of the 8 unknown batteries- 8 tests.

[@binsarm9026]

it's not faulty, that *is* the premise given.

[@Uruz2012]

​@@binsarm9026the premise is that 4 batteries are faulty. As in, 4 batteries do not work. How would one know that 4 are bad before doing the tests?

[@binsarm9026]

@@Uruz2012 maybe someone dropped a box of batteries that they knew the contents of and had to sort them again, it doesn't matter - the point is the method of solving the puzzle *given* - if you want to challenge the interviewer by saying they made a "faulty test" - go ahead, you could maybe score points by being an outlier :P

[@nitehawk86]

These brain teasers are about as useful as a personality test for seeing if someone is fit for a job.

[@-maxx-]

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

[@alejandrocambraherrera8242]

​@@-maxx- You are assuming those test map accurately to real life situations.

[@-maxx-]

@@alejandrocambraherrera8242 not necessarily, but I am assuming they map more accurately than random samples

[@lillones]

You say that now... better hope you don't get squid gamed

[@fdsaa]

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

[@umasankarpadhy8155]

Answer is 6. The question is about finding two good batteries, not about lighting the bulb. after 6 tests (3,3,2) bulb is not lighting then last two are good one...

[@Logan4661]

He said specifically, in writing (include the final test of inserting the 2 good batteries into the flashlight.)

[@RandomThingsOfTheOtherSide]

Assuming the flashlight only works with 2 good ones (i had some flashlighs that only need 1 functioning battery of two to work): Step 1: test any pairs (12, 34, 56,78,37,25.... Basically you need luck) until finding a pair of good ones. Step 2: test both batteries from the the pairs you already tested and came up bad with a good one. Step 3: probably you will have found the remianing good batteries with 2 or 3 tries

[@Sonnell]

Okay, but you can not know if the torch is working correctly... :D

[@indyspotes3310]

The question said "in the worst case". Then the answer is 19.

[@tedjohansen1634]

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.

[@AceBLify]

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.

[@Baldur825]

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.

[@cjlister8508]

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.

[@Matt-qi5ff]

i was doing the dishes while watching the video and also missed the part where they only want 2 good batteries 😅

[@jaredmundi3599]

Confidently incorrect.

[@phamnguyenductin]

This is very similar to the "fake among eight coins" problem where we need to divide them in a 3-3-2 formation.

[@unclegoon347]

I like this 332 solution as it’s a little counter-intuitive to split the batteries into uneven groups… definitely caught me out

[@Silas_MN]

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 😅

[@giantfood1]

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.

[@HappyBeezerStudios]

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.

[@privacyvalued4134]

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.

[@privacyvalued4134]

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.

[@privacyvalued4134]

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.

[@LittleGhost9966]

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

[@MrHowtofall]

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

[@LPC101]

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_Original_forresttrump]

Would love to see a formula devised where no. of batteries =n with no. of good =m where m

[@WunUnknownPlayer]

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.

[@yurenchu]

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.

[@WunUnknownPlayer]

@@yurenchu I see it now. Thanks.

[@yurenchu]

@@WunUnknownPlayer You're welcome!

[@chair547]

I found the 23 solution, optimize it to a 15 solution by realizing that once you've tested battery one with five other batteries you know that it's a bad battery and so on and so forth. Then I watched the video to see how far off I was it felt like I could still do better but I wasn't sure how. You said pair them up and I immediately found the seven solution

[@akwa2273]

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.

[@billiam6398]

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.

[@karlafernanda2715]

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

[@elverdaderoechomikeoscar]

You could divide the bateries in four groups (A;B;C;D) and try one group each time. At worst case you have a good and bad in each. Then try one batery from the first 2. Likely 7 steps to find the first pair of bateries

[@cajonesalt0191]

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.

[@PortRhouse]

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.

[@syx3s]

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.

[@HappyBeezerStudios]

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)

[@brylythhighlights4335]

Divide batteries into 4 pairs (1a/b, 2a/b etc) Test each pair If none of the pairs light up, we know for certainty that each pair is 1 good and 1 bad battery Leaving pair 4b inserted , test 1a and 1b in place of 4a If neither test lights up, we know that 4a is a good battery Leaving 4b inserted, test 1a and 1b Worst case here is 8 tests. edit: Oh hey I got the 'almost good' option :D

[@yixo]

For the first solution you don't have to test the 4th battery 4 times right? You just need 2. You have 5 batteries left and 1 is bad, if the first pairing doesn't light either the stay battery or the test battery is bad so if the next test doesn't light it's the stay battery and if it does it's the one from the 1st test. First one is down to 21. Also if the goal is to just turn on the flashlight and not designate all bad and good, you can on the 4th round of the first test if the first test doesn't light it means you have the bad battery in the pairing so just take 2 of the remaining 3 and turn it on in 20.

[@johnrickard8512]

Optimization 1: there can only ever be 4 dead batteries, so if you test in sequence 4 dead batteries relative to one control, you have proven instead that the first battery is itself dead. Optimization 2: in each analysis cycle, you reduce the number of batteries Optimization 1 must test to determine conclusive fault or function. Optimization 3: a special case will not be needed to escape in the worst case thanks to for() loops evaluating their conditional after the loop executes. Consequently, the algorithm would appear as follows Uint qc-batt[2](){ Uint a = 8 Uint b = a/2 Uint I[a] = seq(mod(rInt(),2), Uint i=0, I

[@aasthavarma2977]

But in the solution with 8 and 7 tests - how to identify the remaining 1 and 2 good batteries, respectively ?