Battery Testing Brainteaser

Our team has recently started working on some brain teasers to sharpen our minds, expose us to new ideas, and keep up our fun factor.

This is our first one:

You are camping with your friends. You have a flashlight for any emergency and have brought 8 batteries along with you. Your brother calls to tell you that four of those batteries are already dead.
Your flashlight requires two working batteries to run. What is the least number of pairs you will need to test to guarantee that you can get the flashlight on?

To clarify, we’re counting the time when you actually load the working pair into the flashlight as a test. So even if you’ve done N tests and now you know for a fact that a certain pair is working, the answer is still N+1 if that working pair isn’t already guaranteed to be in the flashlight.

And “guaranteed” is key. Obviously, it may be the case that the first pair of batteries you test works. That doesn’t mean the answer is one, because in other cases you won’t be so lucky. You need to prove that there is a strategy you can use so that you always find a working pair of batteries within N tries, and furthermore that there is no strategy that will work with fewer than N tries.

Spoiler: Solution and Proof

So below is a solution to this brain teaser. It’s a really interesting problem, so [blah blah blah] ruin the fun [blah blah blah].

The following is based on this answer from math stackexchange.

One way to find the solution is graph theory. We can imagine a (undirected) graph with 8 vertices, and N edges. Think of the vertices as battery holders, and if two vertices are joined by an edge, it means the batteries will be tested together. So the question is: how many edges do we need to guarantee that, no matter how we place the batteries on the vertices, there will always be at least two working batteries joined directly by an edge (i.e., their vertices are adjacent). A more general way to think about it is by coloring the vertices: black for a bad battery, white for a good battery.

I find it easier to think of this problem from an adversarial perspective. So we have a tester, who layouts the edges of the graph (i.e, his test plan), and an adversary who knows which batteries are good and which are bad, and wants to try to place the batteries on the graph in such a way that no good battery is adjacent to another good battery.

The degree of a vertex in a graph is the number of edges that touch the vertex. Our adversary will use the following strategy: identify the vertices with the highest degree and color one of them black. With a vertex black (bad battery), any edge that touches it represents a test where at least one battery is bad, so that test will not find a working pair. So once a vertex is colored black, we can effectively remove the vertex and all the edges that touch it, because we know those tests are going to fail, so they’re no longer interesting to us. After removing the vertex with the highest degree and all of its edges, the adversary repeats this process for a total of four times. At this point, they have removed four vertices, all of them colored black, so the remaining four must be colored white. If there are any edges left, then it must connect two white vertices and there’s nothing the adversary can do about it, so the original configuration worked to find a pair of good batteries.

The tester could use a brute force search to find a pair of good batteries in no more than 28 tests (7+6+5+4+3+2+1). They could also use a few refinements of this to find it in just 15 tests (described below), so we know that the tester could layout a graph with fifteen edges and guarantee that there will be an adjacent pair of white vertices (good batteries). So we could now use a binary search to find the minimum number of edges required.

So we’re starting with 15, we know that’s enough. Let’s try 7.

We have a graph with 7 edges, and 8 nodes; 4 are white, and 4 are black. the handshaking lemma shows that the sum of the degrees of all the vertices is a graph is twice the number of edges, so with 7 edges, the sum of the degrees is 14.

With 8 nodes, if they all had degree of one or less, then the sum of those degrees would be no more than 8. To get to to a sum of 14, at least one of the vertices must have a degree of two or greater. So when our adversary colors the highest degree vertex black and removes it, they are necessarily removing at least two edges. That our graph with no more than 5 edges, and exactly 7 nodes (4 white and 3 black).

With 5 edges, the sum of degrees is 10. Again, with seven vertices, we can only sum to 10 if at least one has degree of 2 or more, so when the adversary removes the highest degree vertex, we will loose another two edges. We’re left with 3 edges and 6 nodes (4 white, 2 black).

With 6 nodes and 3 edges, we can actually already see that this will work out well for the tester, and poorly for the adversary. If the tester creates three disjoint pairs of vertices, the best the adversary can do is force two of those pairs to fail by placing one bad battery in each pair. But that still leaves one pair that much contain two good batteries.

But just to see how this works out, let’s keep going. The sum of degrees is now 6, and we have 6 vertices, so we can only remove one edge, leaving us with 2 edges and 5 vertices, 4 white, 1 black.

The sum of degrees is now 4, so we can only remove one edge again. This leaves us with 4 white vertices, and one edge left, so obviously the edge is going to connect a pair of good batteries, so the tester wins, the adversary looses. In other words, we can use just seven tests and guarantee that we’ll find a working pair. But we haven’t shown yet whether or not we could do it in less.

Before we do, let’s see if we can use this to actually come up with how to do the seven tests. In each step above, we were giving the tester the benefit of the doubt, so as the tester, we need to make sure we arrange our graph to take advantage of that. For instance, in the first step, we said the adversary could definitely remove two edges. Depending on the graph, they may have been able to remove more, but our objective as tester is to make sure they can’t remove all of the edges before they run out of bad batteries. So when we said that the highest degree was at least two, we want to stick to that minimum of two.

So the strategy for the tester seems to be to spread out the edges as much as possible, so that each time they remove a vertex and its edges, it takes as few edges with it as possible. Or, coming back to the batteries, the adversary is trying to force your tests (edges) to fail by making you use a bad battery for that test. The higher the degree of a vertex, the more tests they can force to fail with just a single bad battery.

So our strategy as tester should be to start with each vertex at degree zero, then add one degree to each vertex until we get to the total number of degrees required for the number of edges. For the case of seven edges, we need degrees to total to 14. Giving each of the eight vertices a degree of zero or one clearly isn’t enough, so we start adding one more degree to individual vertices until we reach fourteen. The end result is six nodes with degree two, and two nodes with degree 1, for a total of 14.

Unfortunately, not every graph with those characteristics will actually work. Consider a graph where two vertices form a disjoint pair, and the other six are connected in a cycle. That’s two degrees each with degree 1, and six vertices each with degree 2. However, the adversary could place one bad battery in the pair, and the other three at alternating locations in the cycle, and the setup would fail.

So this may not be a constructive proof: it doesn’t actually show you how to do it, just that it’s possible.

Another possible solution is to break the cycle of six into two cycles of three, and leave the pair. This actually does work. If the pair doesn’t work, there must be at least one bad battery in it, so there must be at least three good batteries between the two cycles of three. That means one of them has at least two batteries in it. Since a cycle of three is fully connected (every vertex to every other vertex), this represents an exhaustive test of all pairs in the set, so which ever of these sets includes the two good batteries, you will necessarily find them.

Intuitively, we probably want each of the sets in our solution to be as fully connected as possible, without exceeding the degree characteristics we found above. To do so, we want all sets to be as small as possible. Much like we did with the degrees, we can build up the sets as needed to reach the required number of edges.

So start with all vertices disconnected (sets of 1). It has zero edges, so we need to start building them up, by joining two of these together. But that’s only one edge, so we keep going.

With four pairs, we still only have four edges, so we’ll need some bigger sets. The next bigger set is a set of three. to get there, we need a single vertex to join to a pair, so we need to split one pair and add one of them to another pair. That gives us one set of three, two pairs, and one single. but that’s only five edges, so we need to make our smallest set bigger.

Our smallest set is a set of 1, but we don’t have any other singles to join to it. We could split up a pair to get another single vertex to join it with, but obviously that will still leave us with the same configuration. So we can’t build up the single into a pair, we’ll have to build up one of the pairs into a set of three, which we can do with the single. That gives us two sets of three, and a pair, which gives us seven edges and happens to be the solution we found above.

But we still don’t know seven is actually the right answer. We know we can do it with seven, but maybe we can do it with six? Or three. We could continue with our binary search, but this is getting tiring, and I actually know the answer is seven, so let’s just do six to make sure.

With six edges, the sum of degrees is 12. We only have eight nodes, so the highest degree must be at least two, so we can remove two edges the first time, leaving us with four edges, three black vertices, and four white vertices. Now the sum of degrees is 8, so we remove two more edges, leaving 2 edges, 2 black, and four white. Sum is now four, so we can only remove one edge, leaving 1 edge, 1 black, and 4 white. Sum is now two, so we can only remove one edge, but that’s the last edge. We have four white vertices left, but no edges to connect them, so six edge is not enough enough to guarantee you find a good pair.

So now what if you have 12 batteries, with six good and six bad? What about four good and eight bad?