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

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

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

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.

Plot Twist: The bulb is burnt out.

missed the opportunity to call half of them baderies

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

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

Try dropping the batteries and seeing if they bounce ;)

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

The optimal construct can be summarized using elementary school Olympiad technics: pigeonhole principal. We have 4 good batteries split into 3 groups of size 3, 3, 2, then at least one group has a pair of good batteries. Then we check every pairs inside each group, that's total 7 pairs to check.

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

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.

14:20 The proof has a gap that I'm sure is fillable, but should be filled: It assumes there is a group of 3 completely disconnected, the group that he "WLOG" chooses 1,2,3. Instead, he should say that this group should exist because: there 8 choose 3=56 groups of three nodes. Each edge can add to 6 groups, when you associate it with the other 6 nodes. So with 6 edges, one can add 6*6=36. However, then one group of 3 must sum less than 1, so that's the disconnected group. In fact, this argument would work with 9 edges, still there has to be a group of 3 disconnected, since 9*6=54<7*8=56.

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.

Around the 14:30 mark, there seems to be a jump in reasoning. It's stated that there is a group with at most 3 nodes with no edges between them. We then continue for the proof by assuming that there is a group with exactly 3 nodes with no edges between them. Note that this can easily be remedied but in the video this step seems a bit off.

We have 28 different ways of combining 8 batteries, 2 by 2, and 6 ways of combining 4. So 22 is the difference. +1 the last test and this gives the same answer 23 to the worst random picking cenario. Now a differnt problem is to optimise this number, making decisions based on the tests already done. Interesting problem, no doubt.

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

Presh's video states and proves that this can't be done in < 7 tests. Can someone please point out the flaw in my logic? My approach was: Randomly arrange the batteries into the following groups: Pair1: 1,2 Pair2: 3,4 Triple: 5,6,7 Single: 8 Test1: Test 1-2 Test2: Test 3-4 Test3-5: Test 5-6,5-7,6-7 Worst case scenario would be if all of the above tests failed, yes? That means there must be exactly one bad battery each in pairs 1&2, and that there must be exactly 2 bad ones in the triple. If that were not the case, at least one of the tests 1-5 would have produced a good pair, no? If that's the case, then that also means that #8 must be good, because there are only 4 bad ones? Test 6: Test battery #8 (which we know is good) against one of the batteries in pair1 or pair2. Doesn't matter which one. If it works, you're done. If it fails, that means the other one in the pair must be good because there is exactly one bad one in the pair. The other one, the good one, plus #8, which we know is good gives us the good pair, no? So this can be done with only six tests? Where is the flaw in my reasoning?

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 ?

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