8 Batteries
You have 8 batteries, numbered 1 through 8. Four of them are good, and four are bad. But you don't know which are which.
You have a flashlight that requires 4 batteries to work. What is the minimum number of times you need to put in the batteries to guarantee to get the flashlight working?
Assume that the flashlight either works (when all four are correct) or not (for any other combination). Nothing in between. And the total number of times includes the final time you put them in, even if at that point you know you have a workable set.
Image credit: http://www.evilcontrollers.com/
The answer is 70.
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.
1 solution
I was over-thinking this for a while, wondering if there might be some kind of strategy to lower the minimum required. No such strategy exists. :)
It may be redundant, but it might be worth considering saying that we do remember which combinations don't work as we go along, (we would have to number the batteries, or something along those lines, in order to remember the combinations we've tried). Otherwise we could potentially go on forever, choosing at random each and every time, yielding no minimum value, (although the expected number of tries would in fact be 7 0 as well).
An interesting follow-up question would be to have 5 good and 3 bad batteries, still requiring 4 good ones to make the flashlight work, and asking for the minimum and/or expected number of attempts.
Log in to reply
Good idea... Lemme update the problem a bit...
Log in to reply
@Brian Charlesworth , I was thinking a much more interesting problem would be 100 batteries where 90 are good and 10 are bad, but I'd need to think a bit about what the optimal solution is... :-P
Any thoughts?
Log in to reply
@Geoff Pilling – Well, my first thought is that there are ( 1 0 9 0 ) combinations that work and ( 1 0 1 0 0 ) − ( 1 0 9 0 ) that don't, so you would potentially have to go through all the latter combinations before being certain that the next combination works. As there are 1 1 , 5 8 9 , 6 6 3 , 9 7 4 , 5 3 7 non-working combinations, this would take a while. :P
However, there is reason for optimism, since the expected number of attempts needed would be ( 1 0 1 0 0 ) ( 1 0 9 0 ) 1 ≈ 3 . 0 2 6 .
@Geoff Pilling – Oh and your flashlight uses 10 batteries...
Log in to reply
@Geoff Pilling – But I was thinking that you could do better than going through all the combinations that don't work.
For example, for the 3x3 case (6 good ones, and 3 bad ones - flashlight takes 3 batteries) There are ( 3 6 ) ways that work, and ( 3 9 ) ways all together. So, ( 3 9 ) − ( 3 6 ) = 6 4 ways that don't work. However, you could get it in much fewer than 64 moves. For example, you could try 1 , 2 , 3 → 1 , 4 , 5 → 1 , 6 , 7 → 1 , 8 , 9 . And, if none of them work you've already figured out that 1 is a bad one in only 4 moves.
Then you try 2 , 3 , 4 ) → 2 , 5 , 6 → 2 , 7 , 8 ) And if none of them work, you've figured out that 2 is bad, and you are at 7 moves.
Finally, you try 3 , 4 , 5 and 6 , 7 , 8 and you know one will work... Bingo! 9 moves!
But, how to prove that it's the best solution... :-/
Log in to reply
@Geoff Pilling – Great strategy! I suppose on the last stage, once one doesn't work you know the other will so you don't really need to test it, making the (proposed) minimum 8 instead of 9 .
With 2 n good batteries, n bad ones and n batteries required, the minimum f ( n ) is such that f ( 1 ) = 2 , f ( 2 ) = 2 , (since if ( 1 , 2 ) , ( 3 , 4 ) don't work you will know that ( 5 , 6 ) will), and f ( 3 ) = 8 , (pending proof). I'm getting f ( 4 ) = 1 4 at the moment:
-
stage (i), if all of ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 5 , 6 ) , ( 1 , 2 , 7 , 8 ) , ( 1 , 2 , 9 , 1 0 ) , ( 1 , 2 , 1 1 , 1 2 ) don't work then at least one of 1 , 2 are bad, (so at most 3 bad batteries remain unidentified);
-
stage (ii), if all of ( 3 , 4 , 5 , 6 ) , ( 3 , 4 , 7 , 8 ) , ( 3 , 4 , 9 , 1 0 ) , ( 3 , 4 , 1 1 , 1 2 ) don't work then at least one of 3 , 4 are bad, (leaving at most 2 bad batteries unidentified);
-
stage (iii), if all of ( 5 , 6 , 7 , 8 ) , ( 5 , 6 , 9 , 1 0 ) , ( 5 , 6 , 1 1 , 1 2 ) don't work then at least one of 5 , 6 are bad, (leaving at most 1 bad battery unidentified);
-
stage (iv), if both of ( 7 , 8 , 9 , 1 0 ) , ( 7 , 8 , 1 1 , 1 2 ) don't work than at least one of 7 , 8 are bad, ensuring that ( 9 , 1 0 , 1 1 , 1 2 ) will work.
Log in to reply
@Brian Charlesworth – One thing... I think f ( 1 ) = 1 , since if you pick one and its bad, you know that either of the other two will be good.
Log in to reply
@Geoff Pilling – Oh, haha, yeah, f ( 1 ) = 1 for sure. :) I tried the sequence 1 , 2 , 8 , 1 4 on OEIS and didn't get any promising hits, so either this problem is too specific or the values aren't right yet. I can't use quite the same strategy in calculating f ( 5 ) as for f ( 4 ) so I suspect generalizing won't be a straightforward task .....
Also, good idea in adding that extra note under "Assumptions", otherwise 6 9 would have been the correct answer.
Log in to reply
@Brian Charlesworth – Haha, it was your comment above that made me think of it... Thanks! ;)
@Geoff Pilling – Also, I wonder if we can generalize f ( n ) ....
Since you get no new information for trying an "incorrect" combination (other than eliminating that combination), you need to try all possible combinations until you get one that works.
And there are ( 4 8 ) = 7 0 possible combinations.