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
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.
Log in to reply
Whoa, good observation! I never stopped to think about the probabilities... Stay tuned for a follow up question! :0)
Great puzzle! Please post more of these.
Better solution, use the bounce test on pairs of 5 batteries.
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!
Ah, very clever! :)
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).
Log in to reply
It's not quite that simple since the untested 50th pair could both be good. See my solution...
Log in to reply
Well, then in picking two pairs one of them shall be the untested one. So it's still valid
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.
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.
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.
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.
Log in to reply
I found this too! I was very excited by reducing the tests to 52 until I found the flaw!
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.
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?
Log in to reply
Ah, very good point, Steven! I'll clarify the problem...
Log in to reply
Worst possible is 4951. Ask me how.
Log in to reply
@Drsabir Momin – You assume you don't test any pair twice.
Split the batteries up in to 5 0 pairs, and test the first 4 9 . If these tests fail, then either:
- the last pair contains two good batteries, one of the previous 4 9 pairs contains none, and all the other contain one good battery,
- all 5 0 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 4 9 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 4 8 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 5 3 tests.
Whoa, this is a great alternate approach, Mark... Thanks for posting!
Worst possible is 4951. Ask me if you do not understand.
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 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!
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.
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.
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.
Worst possible is 4951
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.
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.
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.
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.
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!
This is the proper solution, I also solved the same way and it sounds symmetric and accurate.
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.
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.
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!
4 7 + 6 = 5 3
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...