In cylindrical batteries, Batteries with more charge bounce very little, while discharged batteries bounce more. This test is performed by dropping batteries on their negative terminal. Therefore, assuming these are the standard cylindrical batteries (aa,aaa,d) drop them on their negative terminals, take the 2 that bounce the least, and this problem is solved in “one test” (by the standards of the problem). <a href="#" class="seekto" data-time="105">1:45</a>
@Tamarocker883 күн бұрын
Realistically, each drop comparison of a pair of batteries is considered "one test", so the fastest solution is two tests with the first pair of batteries bouncing high and being confirmed good in the flashlight. Worst case scenario would be 5 tests (first two tests only contain 3/4 bad batteries, requiring a 4th drop test to determine the 2nd of the four good batteries and then finally the test in the flashlight).
@cadencantrell96343 күн бұрын
@Tamarocker88 yes you are correct, but by the wording of the video, this would only be technically considered one test, as a test only occurs when batteries are inserted into the flashlight and it is turned on. If you want to constitute a drop of batteries as a test, then depending on how many you drop at once you would be correct. I just said it was technically one test due to the phrasing of the problem
@NegitoroIsBestShipКүн бұрын
This. Just drop them and observe. Simple.
@GruntpocalypseGaming18 сағат бұрын
they said one test is two batteries in the torch@@Tamarocker88
@commontater6525 ай бұрын
If my boss won't let me use my multi-meter I need a new job.
@useruser4005 ай бұрын
You need a new boss!!!
@AndreasDelleske5 ай бұрын
Solution: Replace boss.
@eman28675 ай бұрын
New problem: There was a mixup at the multimeter factory and your multimeter came with 8 batteries...
@JMMC10055 ай бұрын
@@eman2867 And half of the probes have a broken wire inside.
@commontater6525 ай бұрын
@@eman2867 Well played!
@kbsanders5 ай бұрын
<a href="#" class="seekto" data-time="6">0:06</a> Due to a manufacturing defect = You tried to use batteries from your junk drawer that have been in there for at least 15 years.
@ralfbauerfeind82364 ай бұрын
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. 😉
@charliethunkman3 ай бұрын
Wait, there’s dates on your batteries? All mine say is “ _D __-o-__ _*_n_** t* -R- _3 _*_C_** h* a -r- _ge_ “
@ralfbauerfeind82363 ай бұрын
@@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.
@mydkarthikmecharena90103 ай бұрын
😂
@homemade.bits.03 ай бұрын
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.
@SS-YTChannel2 ай бұрын
Zero tests needed. Throw away all 8 batteries and get four new ones bc an engineer's time is worth more than four batteries.
@robcoop65212 ай бұрын
You mean safely dispose of those batteries.
@SS-YTChannel2 ай бұрын
@@robcoop6521 I didn't say throw them away in an unsafe manner.
@ScottHess2 ай бұрын
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.
@galfisk2 ай бұрын
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
@jarmanjjj10 күн бұрын
sr. software dev here. i got the two ways to test 8 on my own, but not the 7 test technique. very interesting and helpful. thanks! 🏆
@gonecoastal44 ай бұрын
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.
@dirkbester90503 ай бұрын
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.
@gonecoastal43 ай бұрын
@@dirkbester9050 which is why I carry one everyday.
@threeMetreJim3 ай бұрын
And that is why governments overspend.
@ttmfndng2013 ай бұрын
aaaaaaaand... you've failed the job interview
@rmsgrey3 ай бұрын
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.
@doq5 ай бұрын
If your battery supplier has a defect rate of 50% you might want to consider a different supplier. 7 worst case btw.
@tigerboy47054 ай бұрын
Gow do you get 7? Max 5
@myster47754 ай бұрын
@@tigerboy4705So how did you get 5?
@tigerboy47054 ай бұрын
@myster4775 by commenzing way too early and missunderstanding the puzzle xD (didn't get that the flashlight needs 2 batteries xd)
@mr.cauliflower35364 ай бұрын
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.
@Mephistahpheles4 ай бұрын
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.
@Parlik5 ай бұрын
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.
@douglaswolfen78205 ай бұрын
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
@douglaswolfen78205 ай бұрын
(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)
@daudnobel5 ай бұрын
still needed to test the 7 and 8 because there is still a probability 7 and 8 are both good batteries
@allanjmcpherson5 ай бұрын
@@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.
@wizzszz5 ай бұрын
Came here to post that. The other test rounds can be shortened by 2 as well.
@ethanchapman17763 ай бұрын
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.
@yurenchu3 ай бұрын
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.
@gljames243 ай бұрын
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.
@yurenchu3 ай бұрын
None of the presented methods in the video always eliminates half at each test.
@violetquinnlaw16 күн бұрын
@@yurenchu its a battery u test 1 on lips if its charged u keep it, if its dead u toss it. u check next battery on lips if its charged, flashlight has 2 battery's if neither was charged ur 2 bad battery's down 4 good 2 bad to go, continue testing at worst it will take 5 tests to know the rest are good/bad/ identify the 2 groups of battery you can also bounce them, charged batterys have more bounce. alternatively you could use a multimeter or many batterys today have a charge bar on side of them for ppl that dont know how to test them with there tounge NO electrician ever sat there with a pile of batterys putting them in at random to find out which ones where charged. theirs a number of ways of detecting charge level they would use one of them before they resorted to testing with a flashlight in groups of 2, they would at least use a flashlight that held 1 at a time reducing the number of tests to 5 from 11 if you do it with 2 and ur loading 1/2 as many each time also/half the time per test
@yurenchu16 күн бұрын
@@violetquinnlaw The original commenter and I were talking about the methods that were presented in the video, not about what kinds of stunt experiments Johnny Knoxville (or Adam Savage) would do with a bunch of batteries. Furthermore, the question in this video is meant as a logic puzzle, not as a test for the recruitment/hiring of electricians. The principles in this logic puzzle can be used in/extended to all kinds of (data) filtering and (abstract) sorting problems, the "flashlight" and "batteries" are just the dressing up of the problem to make the conditions of the problem more accessible to the general viewership of this math/puzzle channel. Likewise, the so-called "Secretary Problem" is not really about hiring secretaries, and the famous "Monty Hall Problem" does not really apply to any real game show.
@iloshwdgac921315 күн бұрын
Bubble sort never failed me and patients is a virtue for those who asked me for A solution.
@Eduardot1234555612 күн бұрын
I would Split them in two groups of four, test all the combinations in one group, if none of those work It means there's a maximum of one good battery in that group. Then start testing the second group, It would take at most two tests to single out the faulty battery in the second group. So at most It would take 8 tests in total, in the worth case scenario.
@kbsanders5 ай бұрын
Plot Twist: The bulb is burnt out.
@ptorq4 ай бұрын
That's why you need the final test to prove that you've actually been testing the batteries, not the flashlight.
@Fantastic_Mr_Fox4 ай бұрын
what if all batteries were bad? You could theoretically never know.
@josephrissler98474 ай бұрын
Polarity diagram on the flashlight is backwards.
@bothieGMX4 ай бұрын
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.
@kenmore013 ай бұрын
By the time you figured that out, you had been fired.
@Byrnage5 ай бұрын
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.
@sheikyerbouty29264 ай бұрын
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
@lightspeedlagu4 ай бұрын
Great observation! To be fair, 23 is correct for an upper bound. But then so is 100!
@jerkison4 ай бұрын
Yeah but 100! is a little too high to be useful, right?
@lightspeedlagu4 ай бұрын
@@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.
@PhildiusX4 ай бұрын
in 16 test you find all 4 good batteries.
@mickyderheld5 ай бұрын
missed the opportunity to call half of them baderies
@rickkwitkoski19765 ай бұрын
or half of them gooderies!
@samuelcrandall11804 ай бұрын
It sounds a bit too similar to the way "batteries" is usually pronounced to differentiate.
@bignumbers3 ай бұрын
He's an American, so "batteries" is always going to sound like "badderies"
@LoneBeastYT3 ай бұрын
Joke so bad I think you committed "assault" and "badery"
@PWALYM3 ай бұрын
i am sure you will be a good Dad hahaha XD nice dad jokes there :3
@bernym40473 ай бұрын
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.
@Cowtymsmiesznego3 ай бұрын
Apart from it's not the minimum
@matthewwalker49312 ай бұрын
Split in two groups one 3 and one 5 and see how many test you need.
15 күн бұрын
My mind immediately came up with strategy 1, though I suspected you could get by with 1 or maybe 2 less tests. Fascinating video thanks
@howareyou44005 ай бұрын
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.
@ericstelzman51904 ай бұрын
This was on TED-ED. In case you're wondering which video, it's the Giant Iron Riddle.
@Blade.57864 ай бұрын
Oh THAT'S why this reminded me of the sock pair riddle.
@TheDarkNerd4 ай бұрын
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.
@arolimarcellinus85414 ай бұрын
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
@Stratelier4 ай бұрын
@@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.
@MisterVercetti4 ай бұрын
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.
@marcvanwesten27592 ай бұрын
Exactly what I thought
@violetquinnlaw16 күн бұрын
except u can just touch a battery between lips and it it tingles its got a charge. no need to fiddle about with a flash light
@kurtronqx71356 күн бұрын
It's thanks to my familiarity with this puzzle that I had the idea of splitting up the batteries into two groups of 4, then intuitively decided 2 groups of 3 and a pair was much more manageable probability-wise. I forgot how to solve the coin puzzle though so I was flying blind but it turns out I was on the right track 😅
@kathrineici9811Күн бұрын
I think you can use your mouth to solve both questions with varying dangers to your health
@Woztek105 ай бұрын
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).
@douglaswolfen78205 ай бұрын
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
@irrichman5 ай бұрын
@@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.
@chixenlegjo5 ай бұрын
This is actually the same tests as the video’s solution. Your groups are just 123 and 678, rather than 123 and 456.
@황제욱-y1s5 ай бұрын
Perhaps it's even better because the average value is lower
@toastedjam14705 ай бұрын
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.
@FirstLast-gw5mg3 ай бұрын
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.
@thejaskodoth46303 ай бұрын
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-gw5mg3 ай бұрын
@@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.
@ShankarUtthandyV3 ай бұрын
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.. (
@AnaIvanovic4ever10 күн бұрын
Elegant solution, I didnt find the 7 tries one, only 8 tries solution. But, what if the challenge is to find two working batteries as fast as possible, is it still better? My hunch without pen and paper is that the 8 solution requires fewer tries on average than the 7 one?
@petertrzos66458 күн бұрын
@@ShankarUtthandyV it only takes 6 tries because by powers of deduction, if none of your 6 tests lit up, then the remaining untested pair must be good, no test needed.
@billiam63983 ай бұрын
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.
@HansLemurson4 ай бұрын
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_52 ай бұрын
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.
@petertrzos66458 күн бұрын
I attacked it in the same way, and think 6 is the minimum. Check my work! You don't need to do an additional 7th test if none of them light up, because using deductive logic, the remaining pair after 6 rounds of tests must be 2 good batteries. Please check my logic I think I did it in 6 on my first try, and with multiple pathways! Test 1: 1+2 Test 2: 3+4 Test 3: 5+6 Test 4: 7+8 If any of them lit up, you found your good pair in the first 1-4 tests by pure luck. If none lit up, then each pair should have one good, one bad. Test 5: 1+3 = good + good, or bad + bad, or bad + good. If light, you won by #5. Test 6: 1+4 or 2+3 = if either test lights, you win, if they stay dim, you know the remaining pair is 2 good batteries, and you still win.
@asin_58 күн бұрын
@@petertrzos6645 Ah, this a good thought process, the logic being that you use the first 4 tests as a way to obtain 4 good+bad pairs, and then you only need to use 2 good+bad pairs to determine the 2 good batteries within them. However, I disagree that this requires only 2 additional tests for a total of 6 tests. To be explicit with the possibilities, there are 3 cases when taking (1, 2) and (3, 4) as the 2 good+bad pairs and finding that (1, 3) fails the 5th test: Case 1: 1 is good, 3 is bad. Then (1, 4) cannot fail the 6th test because we know 2 must be bad from the 1st test, leaving 4 as the remaining good battery. Case 2: 1 is bad, 3 is good. Then (1, 4) will fail the 6th test, leaving (2, 3) as the pair of good batteries. Case 3: 1 is bad, 3 is bad. Then (1, 4) will fail the 6th test, leaving (2, 4) as the pair of good batteries. By doing the exact same procedure with (1, 3) as the 5th test and (1, 4) as the 6th test, the “remaining pair” you mention is ambiguous, since we encounter 2 possible outcomes when the 6th test fails: (2, 3) as the good pair in case 2, or (2, 4) as the good pair in case 3. I do agree that you have a singular“remaining battery” that need not be tested (battery #2), but we still end up needing to find which battery in (3, 4) to pair it with; to differentiate them, we will require one final, 7th test. Ultimately, what you already state for your 6th test (“1+4 or 2+3”) will need to split into 2 tests. Let me know what you think!
@HansLemurson8 күн бұрын
@@petertrzos6645 If 1+3 is dark, and then 2+3 is also dark, you do know that 4 _must_ be good (and 3 was bad), but you still don't know whether 1 or 2 was the good one. The 1+4 and 2+4 tests are still required. You can argue that after the 7th test, you "know" now, but you still _technically_ haven't lit the flashlight yet. I don't know if that means you have to count the last pairing. 8 "battery insertions" before the light turns on, worst-case scenario. So depending on the definition of success, 7 or 8 tests.
@shanehebert3965 ай бұрын
Try dropping the batteries and seeing if they bounce ;)
@huzefa64215 ай бұрын
Science over Math 😂😂😂
@verkuilb5 ай бұрын
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. 😅
@scottdobson12765 ай бұрын
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.
@HxTurtle5 ай бұрын
I know what you mean, but he kinda thought about this and ruled it out at 0:24 from this imaginary thought experiment.
@WowOafus5 ай бұрын
@@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.
@ReallyAmateurPianist4 ай бұрын
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).
@nixhalla3uk273 ай бұрын
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
@bok48222 ай бұрын
@@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.
@agingerredhead93802 ай бұрын
ah comp sci vs math, get it done or get it done while writing a paper
@alafrosty18 күн бұрын
@bok4822 see my example in the comments. The answer is "6 tests". Logic allows imputed tests that the graphing solution cannot detect. One battery does not get tested and does not need to be tested.
@violetquinnlaw16 күн бұрын
and yet if u used a single battery flashlight or tested it on your tounge by bouncing it or with a multimeter it would be 5 tests of a single batterys not 2 MAXIMUM :P
@AndrewBater6 күн бұрын
I worked out the initial 23, then got a solution with 11 and thought it was such an improvement that I didn't need to look further. Lesson learned.
@UbernoobtuberPC4 күн бұрын
Cool problem! I first jumped to the 4 groups of 2 approach, then after those fail in the worst case, working with just two of those groups. Once I saw the optimal solution, I immediately saw it in terms of combinations. the 8 step approaches being 4 * (2 choose 2) + (4 choose 2) - 2 and (4 choose 2) + 2 * (2 choose 2). The optimal solution being 2 * (3 choose 2) + (2 choose 2) cleverly removes one step, but I feel like it's easy to skip it in consideration due to dividing them into varying group sizes.
@OutrageHarvester5 ай бұрын
Solution: lick finger, hold onto negative terminal, lick positive terminal... if you can feel tingle, it's a good Battery.
@mr.cauliflower35364 ай бұрын
actually, it's still bad, just good enough to tingle.
@ralfbauerfeind82364 ай бұрын
@@mr.cauliflower3536Also, 1.5V might be a little too low for you to "taste" the energy. 🤔
@kenfrank27304 ай бұрын
@@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-3 ай бұрын
@@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-iw6im3 ай бұрын
@PhoenixNL72-DEGA- Same here, it works.
@inplfw5 ай бұрын
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.
@inplfw4 ай бұрын
@@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.
@JMacSD4 ай бұрын
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.
@ilnezija4 ай бұрын
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
@inplfw4 ай бұрын
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.
@peter_castle5 ай бұрын
<a href="#" class="seekto" data-time="860">14:20</a> 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
@andyp58994 ай бұрын
I'm too old to understand what the meaning of edge is
@binsarm90263 ай бұрын
@@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
@physicssquirrel3 ай бұрын
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.
@rmsgrey3 ай бұрын
@@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...
@parkermacinnis397713 күн бұрын
I'm pretty proud of myself on this one. I'm usually stumped by your puzzles, but I got the optimal method right away for this.
@drago58196 күн бұрын
I think I found the seven solution. Putting it in comments before I see the solutions: 12,13,23,78,76,86,45 I initially found a solution that required 10. I decided to try again once I heard the actual optimal numbers. It’s funny how much easier it becomes once you have a goal number.
@drago58196 күн бұрын
Seeing the proof at the ending was interesting, because that’s exactly how I figured it out. I drew out the 8 batteries, and looked for a way I could connect them with 7 lines, with no groups of 4 not connected.
@gowzahr4 ай бұрын
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?"
@kenfrank27304 ай бұрын
During the test say, I'll google that for you.
@stm78103 ай бұрын
already have a light and I don't buy dodgy batteries since I'm not useless.
@Lord_zeel3 ай бұрын
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 😉
@SuperS053 ай бұрын
@@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-gw5mg3 ай бұрын
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.
@verkuilb5 ай бұрын
Duracell gonna sue for using their trademarked color scheme and saying half their batteries are bad. 😂
@XtreeM_FaiL5 ай бұрын
Half of the Duracell's batteries are not bad!
@matthewcodd29395 ай бұрын
This is extremely unlikely to be found infringing, at least because Presh is not advertising any batteries for sale.
@TexasEngineer5 ай бұрын
Duracell leak. I will not buy them anymore.
@Robert080104 ай бұрын
Change it to Energizer, then it will be true! LOL.
@Nupetiet4 ай бұрын
They aren't dead, they're leaky! Get it right!
@cguy965 ай бұрын
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!
@raj1803803 ай бұрын
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).
@fatherrussell530313 күн бұрын
Agreed, this is only something a mathematician would care about. A multimeter is a tool we all have. This test to ferret out candidates will give you a student, not an employee with experience.
@snowthemegaabsol681912 күн бұрын
Tech employees don't have to logically solve problems? This is news to me
@maartendegroot984 ай бұрын
Around the <a href="#" class="seekto" data-time="870">14:30</a> 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.
@ahmedouerfelli47094 ай бұрын
In the basic approach <a href="#" class="seekto" data-time="150">2:30</a> 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.
@Konstamonsta3 ай бұрын
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
@tyranmcgrathmnkklkl3 ай бұрын
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
@MemorywholedАй бұрын
Isn't that assuming battery 1 is good?
@CrypticCobraКүн бұрын
He did that on purpose because option 1 was suppose to be the brain dead brute force method that is “better than nothing”
@carlpierce24865 ай бұрын
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 ?
@verkuilb5 ай бұрын
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?
@josefuher61175 ай бұрын
In the case of (B+1)*M =
@JLvatron5 ай бұрын
Try 'F' for Fail!
@jimi024685 ай бұрын
What about X working batteries, Y broken batteries and Z places for a batteries in the flashlight?
@stevenfallinge71495 ай бұрын
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!
@alafrosty18 күн бұрын
The graphing solution is incorrect because logic allows imputed testing (i.e. deduction).
@NesrocksGamingVideos3 ай бұрын
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.
@glenk75873 ай бұрын
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.
@NesrocksGamingVideos3 ай бұрын
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.
@erendorn3 ай бұрын
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.
@NesrocksGamingVideos3 ай бұрын
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.
@erendorn3 ай бұрын
@@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.
@empmachine5 ай бұрын
This was a really cool one!! Thanks a bunch for sharing!!
@klchu4 ай бұрын
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_Frank3 ай бұрын
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_zeel3 ай бұрын
@@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_Frank3 ай бұрын
@@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.
@fdsaa3 ай бұрын
@@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
@michelcolman3142 ай бұрын
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.
@EmperorZ194 ай бұрын
"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!
@tealkerberus7483 ай бұрын
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.
@rafetizer3 ай бұрын
This was my exact reaction as well lmao
@CaptainFalcoyd3 ай бұрын
@@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).
@arkaig13 ай бұрын
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? ;)
@lawrenceredmacher43823 ай бұрын
8 is 1 more than 7, not 1 short of it. checkmate, math nerds
@thomasnewton29353 күн бұрын
<a href="#" class="seekto" data-time="408">6:48</a> it's not four more tests, it's just 2 more. You're doing more than you have to.
@snowthemegaabsol68193 күн бұрын
It is 4, as there are 4 possible size-2 subsets of set {1,2,3,4}, excluding {1,2} and {3,4} as they have already been tested: {1,3}, {1,4}, {2,3}, and {2,4} 2 tests cannot narrow down which of these will guarantee a success.
@thomasnewton29353 күн бұрын
@@snowthemegaabsol6819 You're right. Must have been overtired and saw some imaginary logic to it.
@dreamsdicc18173 ай бұрын
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
@pannwes5 ай бұрын
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
@ahmedouerfelli47094 ай бұрын
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 ...
@ahmedouerfelli47094 ай бұрын
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.
@pannwes4 ай бұрын
@@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
@yurenchu4 ай бұрын
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!
@yurenchu4 ай бұрын
@@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 ).
@sunilsharma46595 ай бұрын
Me buying 2 new batteries from the nearby store… Problem Solved!
@aaronlewicki80004 ай бұрын
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.
@stm78103 ай бұрын
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.
@kakuwave3 ай бұрын
@@stm7810could just be a different production line
@stm78102 ай бұрын
@@kakuwave Then the answer is eating your boss, actually that's always the answer.no boss means no bad batteries.
@evilkingcaliban4 ай бұрын
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.
@justinmohns82794 ай бұрын
I knew someone would post this! That is the only solution I kept thinking.
@eclipse-sh1qmZ3mOtcua4 ай бұрын
Tell us how to overcome the flashlight's design limitation of requiring 2 batteries. Thanks!
@JaimeWarlock4 ай бұрын
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).
@BartvandenDonk4 ай бұрын
This would only work if the bulb doesn't burn out on 3 good batteries.
@3057luis4 ай бұрын
Yes but....
@The-EJ-Factor2 ай бұрын
<a href="#" class="seekto" data-time="452">7:32</a> this is the best procedure I could think of within a few minutes of the video pause. Curious to see what the 7 step solution is.
@phamnguyenductin3 ай бұрын
This is very similar to the "fake among eight coins" problem where we need to divide them in a 3-3-2 formation.
@unclegoon3472 ай бұрын
I like this 332 solution as it’s a little counter-intuitive to split the batteries into uneven groups… definitely caught me out
@KiraAkaike5 ай бұрын
i thought about the second method because i simply don't have the braincells for the other cases
@3057luis4 ай бұрын
Not that difficult. I also gave up only a bit later
@davileite7803 ай бұрын
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.
@samisuomalainen98703 ай бұрын
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.
@HappyBeezerStudios3 ай бұрын
For that I just pull out my old bike lamp and connect that across any given battery.
@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.
@cajonesalt01912 ай бұрын
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.
@johnywuijts9175 ай бұрын
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)
@skitzocalypso58405 ай бұрын
What happened to your 7th and 8th batteries? 🤔
@Qsalis5 ай бұрын
@@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.
@skitzocalypso58405 ай бұрын
@@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?
@Qsalis5 ай бұрын
@@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.
@Qsalis5 ай бұрын
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.
@Neckhawker5 ай бұрын
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".
@ShawnF6FHellcat5 ай бұрын
Better than me, because I still can't understand it... and I normally excel at math...
@Neckhawker5 ай бұрын
@@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).
@ShawnF6FHellcat5 ай бұрын
@@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.
@stevenfallinge71495 ай бұрын
@@ShawnF6FHellcat"Edge" is a term inherited from geometry, namely the edges of a polygon.
@ShawnF6FHellcat5 ай бұрын
@@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.
@akwa22732 ай бұрын
I didn't finish the video but this is my take. <a href="#" class="seekto" data-time="3050">50:50</a> 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.
@hippophile3 ай бұрын
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!!
@siddharthannandhakumar61872 ай бұрын
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.
@MinePossu2 ай бұрын
At 1:19 said to include the final test. But otherwise 7'th test wouldn't be needed.
@HemanthKs-b1r2 ай бұрын
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!
@jamesw7127 күн бұрын
@@HemanthKs-b1r you failed.
@benoitpoulot-cazajous845 ай бұрын
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
@paulstelian975 ай бұрын
Nice, mathematical proof of theoretical minimum, and the fact that the minimum is in fact possible is great.
@MichaelRothwell15 ай бұрын
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)
@yurenchu4 ай бұрын
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?)
@paulstelian974 ай бұрын
@@yurenchu I guess each test provides _at most_ one bit. Never more.
@yurenchu4 ай бұрын
@@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".
@veezhang69885 ай бұрын
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.
@deept32154 ай бұрын
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.
@OrangiaNebula4 ай бұрын
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.
@rmsgrey3 ай бұрын
@@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.
@Silas_MN3 ай бұрын
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 😅
@MephieStopheles4 ай бұрын
1 "test" Drop each battery on the table. The four that bounce highest are dead.
@dee.daithi012 ай бұрын
i was looking for this one
@Jaszi0073 ай бұрын
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.
@agingerredhead93802 ай бұрын
what it accounts for is the question saying worst case… good job doing an internet buddy
@okrajoe4 ай бұрын
But the job description said no math required?!?
@KatorNia3 ай бұрын
<a href="#" class="seekto" data-time="268">4:28</a> It's 11 tests, not 23. You don't have to test each battery against *all* of the remaining ones, you only need to test the first 5 against each other. Worst case scenario, this group contains at most 1 good battery, so if all tests fail, 6-7-8 are definitely good. Pick any 2 of them for the final confirmation test & you're done.
@yurenchu3 ай бұрын
Actually, _16_ of the 23 tests in the 23-test method can be skipped. So the actual answer is 7 tests.
@KatorNia3 ай бұрын
@@yurenchu Which 7 tests would that be?
@yurenchu3 ай бұрын
@@KatorNia There are several possibilities. The 23-test Method (in the presented order in the video) is: *12* 13 14 15 16 17 *18* , 23 24 25 26 27 *28* , *34* 35 36 *37* 38 , 45 46 *47* 48 , *56* From these 23 tests, we could skip the 16 non-bold tests, and only perform *12* , *18* , *28* , *34* , *37* , *47* , *56* . But *14* , *18* , *23* , *27* , *37* , *48* , *56* also works.
@CrypticCobraКүн бұрын
Sure, except you failed to understand the reasoning this was even explained in the first place. This is the brain dead option in which you just brute force without care to test every possible combination. It’s what a child could think of but at least it’s an answer.
@KatorNiaКүн бұрын
@@CrypticCobra That's an artificially created "bad" method. I mean, with that reasoning you may as well test 1-2 & then 2-1, 1-3 & 3-1 etc, to create 46 unnecessary tests instead of 23. I thought we were talking math, where you don't prove the efficiency of a method by intentionally misrepresenting the efficiency of another. _My comment stands._
@moorishstar11 күн бұрын
Found 8 tests at worst, 1 at best before clicking on the thumbnail. Now I'm writing it down before watching.
@moorishstar11 күн бұрын
As a developer, I loled with the first solution, if it was someone I was interviewing I would be just like: "thank you and good luck dude". The obvious rapid solution for me was the second one.
@todaywelearned3 ай бұрын
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 <a href="#" class="seekto" data-time="734">12:14</a> ! That 7th one is unnecessary, it’s not a “test”, you’re already mathematically positive they work.
@Beast-yp2ei21 күн бұрын
The intro said that you must include inserting two good batteries at the end as a test
@agoosecalledxaro66793 ай бұрын
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.
@jfmrod3 ай бұрын
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?
@agoosecalledxaro66793 ай бұрын
@@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.
@patmenow3 ай бұрын
You didn't listen to the question properly. Haha. It said to include the final test of inserting 2 good batteries.
@adamnevraumont40273 ай бұрын
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.
@tw11tube2 ай бұрын
@@adamnevraumont4027 Your last 7-step solution is equivalent to the 3 3 2 solution. The first triple is 1-2-3, the second triple is 4-5-8, and the pair is 6-7. You perform the tests in a different order, though, and you used a different way to arrive at the same set of tests. Actually, that's not surprising, as it is likely that all 7-step solutions are equivalent. Anyone cares to prove or disprove that?
@Aluzky.Irezumi3 ай бұрын
Tongue the batteries, no need to use a flashlight to see which one works.
@Aluzky.Irezumi3 ай бұрын
Or if it is not a 9volt, you can drop them and the used ones will bounce more.
@josephwilliams19153 ай бұрын
@@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.
@technocolossus3 ай бұрын
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.
@josephwilliams19153 ай бұрын
@@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
@altybro2283 ай бұрын
@@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
@rancidmarshmallow44688 күн бұрын
But which test finds a solution in the lowest number of tests on average, given random distribution of bad batteries?
@philip13823 ай бұрын
I had originally through bad meant the voltage was just low so the pair of 1 good 1 bad wouldn't be enough to use the flashlight but still distinguishable from the pair of 2 bad (i.e. the filament would glow a little). I got to 5 with that assumption but I wonder if there's some clever way to get to 4.
@udayp5 ай бұрын
Being a bit pedantic, @<a href="#" class="seekto" data-time="715">11:55</a>, 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)
@HxTurtle5 ай бұрын
very good spot 👍
@jaideepshekhar46213 ай бұрын
Can you rephrase that?
@HxTurtle3 ай бұрын
@@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.
@thassalantekreskel57422 ай бұрын
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.
@cajonesalt01912 ай бұрын
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.
@JLT91502 ай бұрын
True this
@MechMK14 ай бұрын
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
@bananasunday28453 күн бұрын
You don’t need to do the last test since you already know via process of elimination so it’s 7 😊 By extension of this logic you can actually generalize the answer to n/2+3 tests for n batteries where n is even and half are bad
@WunUnknownPlayer3 ай бұрын
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.
@yurenchu3 ай бұрын
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.
@WunUnknownPlayer3 ай бұрын
@@yurenchu I see it now. Thanks.
@yurenchu3 ай бұрын
@@WunUnknownPlayer You're welcome!
@Wmarsh13ify14 күн бұрын
<a href="#" class="seekto" data-time="445">7:25</a> dont we need to do more tests to find out which 2 good batteries are in 5 6 7 and 8? It took 8 tests to find 2 batteries 2 and 4 <a href="#" class="seekto" data-time="767">12:47</a> wouldnt we still need to figure which 2 batteries are good out of the 2 pairs of 3?
@Ardub2313 күн бұрын
The stated goal was to find (and test) any pair of good batteries, not to identify all four good batteries.
@Wmarsh13ify13 күн бұрын
@Ardub23 ahh thank you! Missed that part!
@noticespams65404 ай бұрын
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'.
@NorthernRealmJackal4 ай бұрын
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.
@ptorq4 ай бұрын
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.
@MrVirus98983 ай бұрын
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.
@AyushMo3 ай бұрын
I'm... so sorry to hear that.. If you're really still looking for a referral, I can help get you one
@LiquidAIWater3 ай бұрын
You should send him a flashlight as a gift with 2 good batteries and the rest bad.:)
@stinkycheese8043 ай бұрын
You obviously did not understand the question and fail miserably. The whole point of the question is to work within the rules presented.
@Ohrami3 ай бұрын
Nice fake story, bro.
@catwithoutthehat3 ай бұрын
Yea just give me a paperclip, or just check if they bounce
@SBK_Sound21 күн бұрын
In real life the flashlight would glow dim with 1 bad & 1 good battery, letting you know that you have a good one, split them into 2 separate piles and then test another pair, if it also glows dim, then leave one and take one from the previous piles, either it will not turn on (swap for the other two), glow dim (swap for the opposite pile) or turn on fully = 3 tests, realistically.
@meyes1098Ай бұрын
I wonder, is there a general formula to figure out the minimum number of tries to guarantee a working pair? To be precise, is there a formula that will work with any given value for the following variables: nrGoodBatteries, nrBadBatteries, nrNeededBatteriesInFlashlight In the video's example, we're working with nrGoodBatteries=4, nrBadBatteries=4, nrNeededBatteriesInFlashlight=2 Is there a formula that gives us the minimum with, say, 4, 10, 3? Or 12,5,4? Or any arbitrary number for these variables?
@Mickey-wh4di11 күн бұрын
"I test 1+2, 3+4, 5+6, 7+8, 1+3 and 1+4 and I'm 93.6% sure. This solution is only mildly significant (p=0.064), exactly like the job you're hiring me for, and that's why I'm the perfect fit"
@JB-kv9zk3 ай бұрын
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?
@yurenchu3 ай бұрын
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.
@Cowtymsmiesznego3 ай бұрын
@@yurenchu "Careless person" a.k.a. I bet most of us have done that at some point
@HappyBeezerStudios3 ай бұрын
@@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.
@rosiefay72833 ай бұрын
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.
@towaii3 ай бұрын
@@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
@jnawk833 ай бұрын
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.
@stinkycheese8043 ай бұрын
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.
@alafrosty18 күн бұрын
The presented solution is incorrect. And I demonstrated how to do it in 6 tests in a couple of minutes.
@andrewhazlewood45693 ай бұрын
The second approach is 7 tests because you don’t need to check 2, 4. You already know 100% that they are both good.
@magicphred3 ай бұрын
yes but you don't identify the other 2 good batteries
@tobiastames52243 ай бұрын
@@magicphred The question isn't to identify all 4 good batteries, it's to identify just 2.
@geirmyrvagnes87183 ай бұрын
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_zeel3 ай бұрын
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.
@syx3s3 ай бұрын
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.
@HappyBeezerStudios3 ай бұрын
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)
@dariodiluciano9443Ай бұрын
The 7 test solution is amazing! Great puzzle, I've come to the first 8 test solution anyway
@ArticulateArena3 ай бұрын
That 7 test is really only 6 in that solution since you dont really need to test the last 2
@stinkycheese8043 ай бұрын
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.
@phoneoperator2 ай бұрын
I just commented this and was looking for this comment as well. 6 is the answer.
@olafbaeyens89553 ай бұрын
No one asked the obvious question: "How did you know that 4 batteries are bad"?
@emberguard50092 ай бұрын
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
@ashton0462 ай бұрын
He said you got the good and bad ones mixed up
@esunisen38622 ай бұрын
@@ashton046 How did he know without having them tested in the first place ?
@majesticsnowleopard2 ай бұрын
Average manufacturing defect rate from that one factory
@CharlesBallowe5 ай бұрын
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.
@irrichman5 ай бұрын
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.
@MrSlerriuqs2 ай бұрын
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.
@PortRhouse2 ай бұрын
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.
@privacyvalued41343 ай бұрын
<a href="#" class="seekto" data-time="40">0:40</a> "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.
@privacyvalued41343 ай бұрын
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.
@privacyvalued41343 ай бұрын
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.
@LittleGhost99663 ай бұрын
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
@MrHowtofall3 ай бұрын
@@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.
@LPC1013 ай бұрын
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.
@indyspotes33102 ай бұрын
The question said "in the worst case". Then the answer is 19.
@tedjohansen16343 ай бұрын
Loads of errors here. Like <a href="#" class="seekto" data-time="635">10:35</a> - 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.
@AceBLify3 ай бұрын
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.
@Baldur8253 ай бұрын
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.
@davidlisteresq2 ай бұрын
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-qi5ff2 ай бұрын
i was doing the dishes while watching the video and also missed the part where they only want 2 good batteries 😅
@jaredmundi35992 ай бұрын
Confidently incorrect.
@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.
@karlafernanda27152 ай бұрын
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
@yurenchu12 күн бұрын
It is the same seven test pairs as in the 7-test procedure in the video, but in a different order (and labeled differently). But indeed, your order is the most efficient order of the 7 pairs, while the video's order is the least efficient order of the 7 pairs. (Less efficient than the presented 8-test solution, even.)
@Sonnell5 ай бұрын
Okay, but you can not know if the torch is working correctly... :D
@nitehawk863 ай бұрын
These brain teasers are about as useful as a personality test for seeing if someone is fit for a job.
@-maxx-3 ай бұрын
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
@alejandrocambraherrera82423 ай бұрын
@@-maxx- You are assuming those test map accurately to real life situations.
@-maxx-3 ай бұрын
@@alejandrocambraherrera8242 not necessarily, but I am assuming they map more accurately than random samples
@lillones3 ай бұрын
You say that now... better hope you don't get squid gamed
@fdsaa3 ай бұрын
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
@giantfood13 ай бұрын
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.
@HappyBeezerStudios3 ай бұрын
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.