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

This is a famous problem that has been used in technical interviews, and it has even appeared on a Mathematical Olympiad. There are 4 good batteries and 4 bad batteries, and you need to insert 2 good batteries to make a flashlight work. How many tests do you need?

0:00 problem
1:53 estimate
5:18 strategy 1
7:47 strategy 2
10:46 solution
13:08 proof

Bogumił Kamiński
Brazil Olympiad
StackExchange
Mike Pawliuk
Glassdoor
LogicallyYours

Send me suggestions by email (address at end of many videos). I may not reply but I do consider all ideas!

If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.

If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.

Book ratings are from January 2023.

My Books (worldwide links)

My Books (US links)
Mind Your Decisions: Five Book Compilation
A collection of 5 books:
"The Joy of Game Theory" rated 4.3/5 stars on 290 reviews
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" rated 4.1/5 stars on 33 reviews
"40 Paradoxes in Logic, Probability, and Game Theory" rated 4.2/5 stars on 54 reviews
"The Best Mental Math Tricks" rated 4.3/5 stars on 116 reviews
"Multiply Numbers By Drawing Lines" rated 4.4/5 stars on 37 reviews

Mind Your Puzzles: Collection Of Volumes 1 To 3
A collection of 3 books:
"Math Puzzles Volume 1" rated 4.4/5 stars on 112 reviews
"Math Puzzles Volume 2" rated 4.2/5 stars on 33 reviews
"Math Puzzles Volume 3" rated 4.2/5 stars on 29 reviews

2017 Shorty Awards Nominee. Mind Your Decisions was nominated in the STEM category (Science, Technology, Engineering, and Math) along with eventual winner Bill Nye; finalists Adam Savage, Dr. Sandra Lee, Simone Giertz, Tim Peake, Unbox Therapy; and other nominees Elon Musk, Gizmoslip, Hope Jahren, Life Noggin, and Nerdwriter.

My Blog

Twitter

Instagram

Merch

Patreon

Press

[commontater]

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

[kbsanders]

0:06 Due to a manufacturing defect = You tried to use batteries from your junk drawer that have been in there for at least 15 years.

[doq]

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

[mickyderheld]

missed the opportunity to call half of them baderies

[Parlik]

The first example did more tests than was needed with that method.
After testing 1 with 2 to 6, and the flashlight didn't turn on, there is no need to test with 7 and 8, as you must have tested 1 with at least one good battery in the other slot, and since the flashlight didn't turn on, 1 must be bad.

[Byrnage]

In the first example the maximum number of tests should be 15 i think. After 5 tests you will know if your first battery is good or not. You will have to have hit at least one good battery at that point and if the flashlight never turned on then your first battery is clearly dead. There is no need to continue testing that battery.

[MrVirus]

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.

[gonecoastal]

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.

[shanehebert]

Try dropping the batteries and seeing if they bounce ;)

[Woztek]

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

[howareyou]

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.

[OutrageHarvester]

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

[verkuilb]

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

[EmperorZ]

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

[ReallyAmateurPianist]

Really fun puzzle!

As an additional note, I think you can also show that 6 tests is never enough with simple brute-force coding:


1. Generate all possible combinations of good and bad batteries. There are a total of 70 such combinations (8 choose 4).


2. Generate all possible combinations of 6 tests. There are a total of 376 740 such combinations: 28 possible tests (8 choose 2), which gives "28 choose 6" = 376 740.


3. Then execute each 6-test combination for each combination of good and bad batteries.


4. As the end result, you should see that for all 6-test combination, there will be at least one combination of good and bad batteries where all tests leave the flashlight unlit.


5. This is a total of 26 371 800 (376 740 * 70), which should be easily doable for a computer.

Quite an ugly way of doing it, but still a valid proof. (But I still prefer a nicer proof via graphs).

[inplfw]

My gut led me to 8 tests Presh presented as solution 2. I don't think I would've gotten the 7 test solution if thought about it longer. Interesting problem.

[peter_castle]

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

[KiraAkaike]

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

[gowzahr]

I've never been in an interview where a question like this was asked, but it seems like the amount of time that would be given to answer wouldn't be sufficient to figure out the best answer. So, it just becomes a game of, "Did you Google common interview questions and memorize the answers before hand?"

[gljames]

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.