Find the minimum number of attempts to select a usable battery
Recently I came across an interesting puzzle at The return of the graphs (and an interesting puzzle)
You are given eight batteries, out of which four are good and four are depleted, but visually they do not differ. You have a flashlight that needs two good batteries to work. You want your flashlight to work. What is the minimum number of times you need to put two batteries into your flashlight to be sure it works in the worst case.
There are 8 batteries in total, and there are 28 ways to choose 2 of them, and 6 ways to choose 4 of the good ones, so even if you put them in the flashlight without thinking, you can be sure that it will work on the 23rd try.
But of course it is possible to get it to work in fewer attempts, and the correct answer is 7.
It is easy to see that 7 times is enough: if we divide the batteries numbered from 1 to 8 into three groups {1, 2, 3}, {4, 5, 6}, {7, 8}, somewhere in the group will be at least two good ones. So, we should try all pairs within each group, and the number of times is $3+3+1=7$.
Proving that 6 times is not enough is a bit complicated, so please see the blog at the beginning of this article.
Interestingly, this problem can also be approached as a graph problem. Prepare a graph with 8 nodes, and consider that when there is an edge between nodes $i$ and $j$, the corresponding battery is put into the flashlight.
For example, a pattern that works well with 7 comparisons can be represented as the following graph.
1 4 7
/ \ / \ |
2---3 5---6 8
Then the question to consider is “In an undirected graph with 8 nodes and $E$ edges, can the maximum size of a subset of nodes with no edges between them (called an independent set) be less than 3?” If there is an independent set of size 4 or larger, then no good pair can be found if all the good nodes are in it. On the other hand, any independent set can satisfy the condition if its size is less than 3.
For example, even if there are 7 edges, if we create a graph like
1 4 7
/ \ / \
2---3--5---6 8
then {1, 4, 7, 8} will be an independent set of size 4, and these will be undiscoverable in the case of a good.
If we can arrive at such a problem, the rest can be solved by brute force with the help of a computer. We can enumerate all possible graphs for each number of edges and check whether the condition is satisfied. Specifically, starting from the graph with zero edges, repeat the following steps:
- Enumerate all graphs with $E+1$ edges by adding one edge in any pattern to the graph with $E$ edges. Combine isomorphic graphs into one.
- Find the maximum size of the independent set of nodes for each graph.
- Find the minimum value of this maximum size for the entire graph of $E+1$ edges.
- If this minimum is less than or equal to 3, you are done.
The Julia code in the blog did not work in my environment, so I have rewritten it in Rust:
