4
$\begingroup$

I have a solution to the following brainteaser, which I think is the correct answer, but I haven't been able to come up with a way to prove that it's the right answer. I know very little about graph theory, and even less about Ramsey theory, but this feels applicable.

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?

Note that the final time you load the working batteries into flashlight counts as a test, even if you already know that the pair works.

My solution is as follows (spoiler):

Partition the batteries into four disjoint pairs. Test each pair. If any of them work, great, you're done. If none of them work, you know that each pair has exactly one good battery, and one bad battery.

Now take two of the four pairs. Test each battery from one pair with each battery of the other pair. I.e., if the pairs are $(A,B)$ and $(C,D)$, then test $(A,C)$, $(A,D)$, $(B,C)$, and $(B,D)$. Since one of $A$ and $B$ works, and one of $C$ and $D$ work, one of these four trials will work.

So the total number of tests is eight, and you're guaranteed to find at least one pair of good batteries.

Note: Sisi has offered a better solution in the comments which can do it in seven tests.

I know my solution works to find a working pair, but how would I prove that there isn't a way to do it in fewer tries (or, if there is a better solution, how would you prove that it is the best solution)?

$\endgroup$
  • 4
    $\begingroup$ I can do it in 7 times. If you partition your 8 batteries into 3,3,2 groups. 3 times in the first group. 3 times in the second. And 1 time in the last group. $\endgroup$ – Sisi Jul 15 '15 at 16:41
  • $\begingroup$ @Sisi Good catch, thanks! $\endgroup$ – brianmearns Jul 15 '15 at 16:55
  • $\begingroup$ you can easily prove this numerically, also most people would be happy with just a logical argument (why is it forbidden to use our brains) $\endgroup$ – john Jul 15 '15 at 19:38
  • $\begingroup$ @john I'm not sure what you think I'm looking for, but I would actually prefer that you use your brain to answer. I don't care, and didn't specify, what type of proof you use, the point is just that coming up with a way to test the batteries isn't sufficient, you also need to prove that you can't do it in fewer trials. So if you can "easily" do it, I'd love to see it in an answer. $\endgroup$ – brianmearns Jul 16 '15 at 10:21
2
$\begingroup$

As @Sisi noted, you can find working pair in $7$ tests by splitting the batteries $3,3,2$.

Now, how could we prove that no $6$ tests suffice? The tests one does can be represented as edges in a graph of $8$ vertices. We would like to prove that we can color $4$ vertices of the graph black (dead), so that no edge gets both of its vertices white (working), that is, that there always exists a (black) vertex cover of size $4$.

To do this, pick the vertex of the highest degree, color it black and remove from the graph with all its incident edges. If we have removed three or more edges, then there are at most 3 left which are easy to cover with the remaining 3 black vertices. If we have removed two edges, then the next vertex of the highest degree (in the smaller graph) also has degree at least 2 (since we have 4 edges remaining and 7 vertices). In this case, we remove two more edges and its easy to cover the rest with the remaining two black vertices. This concludes the proof.

Edit: The previous version was wrong, thanks to @Greg Martin for pointing out the flaw.

I hope this helps $\ddot\smile$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think this is definitely the right idea, but your current proof seems flawed. Imagine that five of the six edges have a common endpoint - that makes a star with six vertices - and the last edge connects the other two vertices. Your algorithm doesn't say what to do with ties, so it's quite possible that neither of the last two vertices gets assigned "dead". (The specific line I don't believe, in other words, is "That means for each of these the other vertex is black".) $\endgroup$ – Greg Martin Jul 15 '15 at 17:25
  • 1
    $\begingroup$ Very helpful answer, but I agree with Greg, I'm not seeing the final conclusive step to the proof, and it doesn't even require a tie. Imagine for instance you have four vertices connected in a ring. They each have degree two, so we color them black. The remaining four are connected as two disjoint pairs, so each has a degree one, and is colored white. But each white connects to another white, so this configuration of six edges works. Of course, that doesn't prove that you can guarantee finding a match with six tries as required by the riddle, but I don't think this answer has proven you can't. $\endgroup$ – brianmearns Jul 15 '15 at 17:42
  • $\begingroup$ @GregMartin Thanks, should be fixed now! $\endgroup$ – dtldarek Jul 15 '15 at 21:20
  • $\begingroup$ @dtldarek Thanks, that's a great answer! For those interested, I worked through this in a lot more (painstaking!) detail here: boldlyforward.wordpress.com/2015/07/16/… $\endgroup$ – brianmearns Jul 16 '15 at 20:30
  • $\begingroup$ @sh1ftst0rm I'm glad you like it. If math.SE was helpful to you (e.g. the comment of Sisi) then I think that it would be appropriate to link here (i.e. your question) from your blog post. $\endgroup$ – dtldarek Jul 16 '15 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.