100 Batteries

You go into your garage and find a pile of 100 batteries (all the same type).

You happen to know that half of them are good and half are bad, but you can't tell which is which.

You have a flashlight which uses two batteries, and requires both to work in order to turn on.

In the worst case scenario, with an optimal strategy, what is the minimum number of times you will need to put batteries into the flashlight before you can guarantee to get a working pair in the flashlight?


Details and Assumptions:

  • The flashlight either turns on or it doesn't, i.e. there is no way to distinguish between one of the two working and neither one working.

  • Your answer should be the number of "flashlight loadings" you will need to actually get your flashlight working, not just how many you would need to identify two good batteries.


Image credit: https://www.slrlounge.com


The answer is 53.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Geoff Pilling
Jan 11, 2017

You can do it with 53 "flashlight loadings" as follows:

Form 47 pairs of two, and try each one out.

At this point, either the flashlight lit up (and you are done), or it didn't.

If it didn't, then at worse, there were 47 good batteries in the previous lot. So, you know that at least 3 of the remaining 6 are good.

So, then divide these six up into 2 groups of 3 and one group is guaranteed to have a good pair in it.

So, try each of the combinations within each group of three. (That is six trials all together) And, one is guaranteed to get the flashlight working!

47 + 6 = 53 47+6 = \boxed{53}

Thanks to @Brian Charlesworth for pointing out the error in my original solution which took 54 "flashlight loadings".

I will try to come up with a rigorous proof as to why you can't do it with fewer...

I agree that to be 100% certain you would only need 53 attempts. In fact you'd only expect to have to try 4 pairs on average. And the probability of getting to 47 pairs not working is very very much less then 0.75^47 since there's some chance that failing pairs contains two bad ones, so increasing the probability of finding two good batteries in the next pair. I estimate than 1 in 10^16 for the probability.

Ed Sirett - 4 years, 4 months ago

Log in to reply

Whoa, good observation! I never stopped to think about the probabilities... Stay tuned for a follow up question! :0)

Geoff Pilling - 4 years, 4 months ago

Great puzzle! Please post more of these.

Siva Bathula - 4 years, 4 months ago

Log in to reply

Thanks... I'll try! ;-)

Geoff Pilling - 4 years, 4 months ago

Better solution, use the bounce test on pairs of 5 batteries.

Razzi Masroor - 4 years, 4 months ago

Log in to reply

Sadly, since all the batteries in the pile in the garage are likely to have been around a while, this research from Princeton indicates that the bounce test will not work!

Mark Hennings - 4 years, 4 months ago

Ah, very clever! :)

Geoff Pilling - 4 years, 4 months ago

I had another 53 one, namely try 49 pairs. In the worst case, each pair has exactly one good battery in it.Then you pick two pairs and try all remaining combinations (there are 4).

Paul Paul - 4 years, 4 months ago

Log in to reply

It's not quite that simple since the untested 50th pair could both be good. See my solution...

Mark Hennings - 4 years, 4 months ago

Log in to reply

Well, then in picking two pairs one of them shall be the untested one. So it's still valid

Paul Paul - 4 years, 4 months ago

Log in to reply

@Paul Paul But that approach leaves you with possibly five tests to make - four to test the members of one pair against the members of the 50th pair, and also the members of the 50th pair against each other (the worst-case scenario is the you have two duds in the old pair and two goods in the 50th pair). My solution tells you how to avoid the fifth extra test.

Mark Hennings - 4 years, 4 months ago

I will try to come up with a rigorous proof as to why you can't do it with fewer...

I suggest first proving that the best method will be a "partition and exhaust" method. (I don't know if there's an official name for that. By "partition and exhaust" I mean partition the 100 batteries into 49 groups -- one fewer than the number of good batteries, cf. pigeonhole principle -- then perform a test on every possible pair within every one of those groups.) Once that is established, it's quite easy to verify that the number of tests is minimized by making the groups as "even" as possible, e.g. 47 size-two groups and 2 size-three groups is better than 48 size-two groups and 1 size-four group.

Peter Byers - 4 years, 4 months ago

I think the answer is 52. Finish 48 pairs. Then 4 left to choose from and there are 4 more possible combinations to get to working pair. So I reckon it to be 52.

Faisal Bashir - 3 years, 6 months ago

Log in to reply

The worst-case scenario is that the last 4 contain 2 good batteries. This leaves 6 possible combinations to consider, not 4.

Mark Hennings - 3 years, 6 months ago

Log in to reply

I found this too! I was very excited by reducing the tests to 52 until I found the flaw!

Philip Guest - 3 years, 2 months ago

if you make 47 pairs, the following cases might occur:

CASE1: in that 47 pairs you have a good pairs which is at last(at the 47th trials) thus making 47 trials.(this is not the worst case)

CASE2: In that 47 pairs at you have a pair of bad and the 46 rest are composed of Good-Bad pairs, thus at the end you have to test the other 3 remaining pairs since 1 of them will need to have a pair of good making the total trials 50

CASE3: In that 47 pairs you have only pair of Good-Bad and so does the last remaining 3 but actually you don't know that, so you have to test all 3 pairs to check if there is a pair of good one making a total of 50. Now after you've done that and still the torch doesn't light, at that moment you know that there is no pairs of Bad-Bad (which in turns will result a pair of Good-good). So now you can take any two pairs and test them and the worst combination will be as follows:

At first you have Bad-Bad, so you remove 1 of them placing a Good(this combination is Bad-Good) one there and noticed it doesn't work so now you know that the first battery is Bad and you remove it placing another battery which is a bad one making the combination (Good-bad) and finally Good-Good 1.Bad-Bad 2.Bad-Good 3.Good-bad 4.Good-good.

Thus in total making 54 trials.

yasseen N - 3 years, 1 month ago

I agree with your procedure. That's what I came up with. Nice problem.

But I thought you would be "guaranteed to get" a working pair before trying the last two. Of course, most folks (except perfectly logical mathematicians) would try them just to be certain.

So my first answer was 53. Perhaps the wording of the problem could clarify that you expect a working pair in the flashlight?

Steven Perkins - 4 years, 5 months ago

Log in to reply

Ah, very good point, Steven! I'll clarify the problem...

Geoff Pilling - 4 years, 5 months ago

Log in to reply

Worst possible is 4951. Ask me how.

Drsabir Momin - 3 years, 6 months ago

Log in to reply

@Drsabir Momin You assume you don't test any pair twice.

Paul Paul - 3 years, 6 months ago
Mark Hennings
Jan 20, 2017

Split the batteries up in to 50 50 pairs, and test the first 49 49 . If these tests fail, then either:

  • the last pair contains two good batteries, one of the previous 49 49 pairs contains none, and all the other contain one good battery,
  • all 50 50 pairs contain one good battery.

At this stage test one of the batteries from the last pair against both batteries from any one of the earlier 49 49 pairs. If the last pair contains two good batteries, and the other pair contains one good battery, we will get a match. Otherwise we can deduce that the other battery in the last pair is good, and all the other previously-tested 48 48 pairs contain one good battery each. Thus we can now test the second battery from the last pair against the two batteries in any other previous pair, and we will find a match.

This gets us a match after at most 53 53 tests.

Whoa, this is a great alternate approach, Mark... Thanks for posting!

Geoff Pilling - 4 years, 4 months ago

Worst possible is 4951. Ask me if you do not understand.

Drsabir Momin - 3 years, 6 months ago

At this stage test one of the batteries from the last pair against both batteries from any one of the earlier pairs. If the last pair contains two good batteries, and the other pair contains one good battery, we will get a match. Otherwise we can deduce that the other battery in the last pair is good, and \textbf{and} all the other previously-tested pairs contain one good battery each. Thus we can now test the second battery from the last pair against the two batteries in any other previous pair, and we will find a match.

This AND should be a OR. And it gives us the 54th try making it under optimal!

Alexandre Boisson - 2 years, 7 months ago

Log in to reply

No, the second case must then have happened

Johannes H - 2 years, 5 months ago

I guess in order for this alternate approach to work one precaution must be observed. After testing the first battery from the 50th pair the second one should be tested against any of the previously tested pairs "except" the one we tested at 50th and 51st trial. (Let G stand for good and B for bad). There are two possible scenarios. 1. 50th pair GG, one of the previous pairs BB 48 pairs BG
2. All pairs including 50th GB.
Let us take the second scenario first. For the worst case scenario we pick B from last pair, then test it with any of the previous pairs. We will fail twice thus making it 51. Now pick the other one which is a G and test it against any other pair "except" the one we tested earlier (In this case it will work if you test it against 'any' pair but not in the second scenario). In the worst case scenario you will find the right pair in 53 tries.
Now see the first case. You pick up a G and in the worst case scenario test it in turn with each in the pair of BB without success. That makes it 51. Now pick up the second one which also is a G and compare it against any other except the first one (BB). You will succeed at the most in 53 attempts. If you carefully follow this strategy you will definitely work it in 53 attempts or less.


Zahid Hussain - 1 year, 11 months ago
Charlz Charlizard
Jul 10, 2017

Here, make 50 pairs of batteries and check all 50 of them.In the worst case scenario none of them are good pairs(Containing batteries with working conditions).This implies all the pairs have 1 good and 1 bad battery.So take any 2 pairs of batteries, let's say (1,2) (3,4) are the pairs.Here suppose, for the simplicity of explanation, that odd(1,3) ones are bad and even ones are good(2,4).In the worst case we happened to try (1,4),(2,3) both didn't worked.And then we tried (1,3) and if this didn't lit up the torch,then the only left pair(2,4) is a good pair.This in total, makes 53 conditions to be checked before we get the good pair of batteries. And the general solution for the similar problem is (N/2+3) where N is total number of batteries(N is considered even)

This would give you 54, as you'd then need to load the good pair of batteries one last time in order to light up the flashlight to fulfill the rules of the problem.

William Wight - 3 years, 10 months ago

Log in to reply

Here even if one does not check the last pair, one can still assert that he/she has found the right pair of batteries.

Charlz Charlizard - 3 years, 7 months ago

Worst possible is 4951

Drsabir Momin - 3 years, 6 months ago

Log in to reply

Can you elaborate your answer? Because in other scenarios, you can have 2 good batteries too, in a pair, and so that's not a worst case.In fact it will give take less number of tries to find a good pair.You can also calculate the probability to substantiate the answer.

Charlz Charlizard - 3 years, 3 months ago

I am sorry. I am not clearly understand condition because of I am not a native english person. I don't think so. If we have two batteries and one of them is good and one of them is bad, than flashlight should work. I don't see in the condition that the second battery is defined completely bad, so the currency could not go through it. I don't think, that just bad battery could not work with another working battery as a usual conductor. In this case your the worst case is if you take 25 pairs of bad batteries. The other 25 pairs are good by definition.

Grigoriy Yuschenko - 2 years, 10 months ago

Log in to reply

Hello, I am not able to understand your point. Can you start by giving the answer, you think is correct? So that I can analyse your argument on that basis. Thank-you.

Charlz Charlizard - 2 years, 10 months ago

Well problem stated that one bad would fail to light the lamp. Se it as a led lamp that will not turn on unless you have the needed voltage.

Juanito Skomars - 2 years, 4 months ago

Worst Possible means "the most ammount of 'X' "/batteries needed to test. The Best Possible means "the least about of 'X' "/batteries needed to test Just a helpful tip!

Michael Hibler - 6 months ago

This is the proper solution, I also solved the same way and it sounds symmetric and accurate.

Sparsh Singh - 2 months, 3 weeks ago
Dabang Panday
Mar 18, 2019

51 can be the answer. If first 48 pairs didn't work then for the remaining 4 batteries, it can take max 3 tries to find the working pair.

So 48 + 3 = 51.

Justin Park
Jul 26, 2019

First, you take any 4 of the batteries and check all 6 possible combinations. In the worst case scenario, they will all fail, determining that they were all bad batteries.

Then, you take another 46 batteries and pair them into 23 groups. They will all fail in the worst case scenario, revealing that they were all pairs of good and bad or both bad batteries. There has to be at least 23 bad batteries in the pile of 46 batteries.

Similarly, you take 46 batteries again and pair them into 23 groups. Again, all failed in worst case scenario. We know that we need at least 23 bad batteries for this to happen and look. 4+23+23 = 50.

We confirmed all the bad batteries in the pile. Therefore, the remaining 4 batteries must be all good ones and we can check any of them to finish the puzzle. 6+23+23+1 = 53.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...