(After writing some posts directed at other mathematicians, here is one for everybody.)
I was sifting through some old issues of Crux Mathematicorum last Friday. For those of you who don’t know, this is a wonderful magazine that contains tons of math questions generally like those you would see in a math contest or olympiad, and the difficulty ranges from elementary school to undergraduate. In the September 2009 issue, I stumbled upon the following nice problem originally from the 2005 Brazilian Mathematical Olympiad. It is one of those problems that is mathematical in flavour and doesn’t need any previous math knowledge to begin thinking about the problem. For me, a nice problem is one that rewards you for thinking about it and can be attacked from many different angles.
So here’s the problem as stated:
We have four charged batteries, four uncharged batteries, and a flashlight which needs two charged batteries to work. We do not know which batteries are charged and which ones are uncharged. What is the least number of attempts that suffices to make sure the flashlight will work? (An attempt consists of putting two batteries in the flashlight and checking if the flashlight works or not.)
Makes sense right? We’ve got 4 live batteries, 4 dead batteries and we need to find 2 that are live. So go ahead and think of a strategy, any strategy and see if you can find two batteries that work using less than, say, 20 attempts. Do it, grab a pen and a piece of paper if you need and try something. I’ll wait.
Alright. You might have some questions now.
Do I know what batteries I have already checked? You sure do! You can even label them if you want.
How many batteries were there again? 8 in total: 4 live, 4 dead.
Can I start with a live battery? Well you won’t know if the first battery you grabbed is a live battery. If you did know that you had a single live battery you could just check it against 5 other batteries and you would be guaranteed to find a working pair.
How many total pairs are there? 28. (This is 8 choose 2, and you can just ask google). If there were only 4 batteries, there would be 6 pairs. You can figure out for yourself (either by hand or by using your new Google-fu) how many pairs there are if there were 3 batteries.
Now that you know that, look at your strategy again and see if you can make it a little better. Or maybe these answers have inspired you to think of a better strategy!
Great, now lets look at how you did. Here are a couple different strategies that I’ve heard:
The Gorilla Method (i.e. the not very smart way, that takes a lot of work, but is guaranteed to work) – We know that there are 28 total pairs, and of those there are 6 pairs that are working pairs. So let’s just try them all. After I’ve tried 22 different pairs that don’t work, I’ll know that the next pair I try will have to work. So this tells us that the worst possible method takes 22 attempts.
The 1-2-3-4 method– The idea here will be to find, one-by-one, all of the dead batteries. So take a battery (A), and check it against 5 other batteries. (You can’t just check 4 other batteries, because you may have started with a live battery, in which case you might have just checked it against 4 dead batteries.) If none of the pairs work then (A) must be a dead battery. Now do the same with (B), but this time you only need to check it against 4 batteries (don’t check it against A which you know is dead!). Then check (C), which takes 3 attempts, and (D), which takes 2.
So now you know that A,B,C and D are the dead batteries, so any of the remaining two batteries work. This took us 5 + 4 + 3 + 2 = 14 attempts. Getting better!
The Divide and Conquer method– There are variations on this method, but they are all pretty much like this. Divide the 8 batteries into two piles, Pile 1 and Pile 2. (For the french readers, there was no pun intended.) Check all the 6 different pairs in Pile 1. What happens if none of the pairs work? Think about this. How many dead batteries must be in Pile 1 if none of the pairs work?
Well the answer isn’t 2, because then one of the pairs would contain two live batteries. So there must be at least 3 dead batteries in Pile 1. So now divide Pile 2 into two pairs (Pair 1 and Pair 2). Try Pair 1. If it doesn’t work, then you’ve found the last dead battery, so Pair 2 must work!
How did we do here? 6 + 1 = 7 attempts. Not bad at all! But we can do better…
The Triplet method– This is a lot like the divide and conquer method, but we do more dividing and more conquering. Here’s the picture; see if you can tell what is going on, and how many attempts it will take. (Hint: there are 3 different pairs if there are 3 batteries.)
This is the best method I could come up with. Not so bad, right? It gets the job done in 6 attempts. Is it the best though? I don’t know. What do you think? Post any ideas you have in the comments below. I’m also interested in which method you tried first. I have a guess that mathematicians are more likely to pick the divide and conquer method first.
Which method did you first come up with? | |
Gorilla method | |
1-2-3-4 method | |
Divide and Conquer method (any type) | |
Other | |
pollcode.com free polls |
(Thanks to Brandon Hanson, Seth Sundburg, Nathan Gilbert and Janet Mowat for their help with this post.)
Hi, interesting question! I think you have got the answer. I think I have shown that your answer is correct.
First we reformulate it in graph theoretical terms: Let G be the graph obtained by the complete bipartite graph , where we also add all possible edges among vertices in a chosen partition class (alternatively, pick four vertices in and make them independent). This models the “non-working” pairs of batteries.
Now the question is, what is the minimum number of edges for a graph on 8 vertices which is not a subgraph of G? (call such a graph “bad”)
You’ve shown the answer is at most 7, namely the graph obtained by two disjoint 3-cycles and a disjoint
edge. We’ll show this is optimal.
Let H be a graph with 8 vertices and 6 edges. I will find four vertices which have no edges between them.
H has total degree 12, so by removing the highest degree vertex we have 7 vertices and at most 4 edges.
There are two cases:
(i) there are 4 edges remaining, in which case we have total degree 8 and hence one vertex has degree 2.
(ii) there are <4 edges remaining.
In either case by removing the highest degree vertex we have 6 vertices and at most 2 edges.
By doing it again we have 5 vertices and at most 1 edge. By doing it a final time we have the four vertices we were looking for.
LikeLike
Thanks! This is a great write-up of the lower-bound.
(Sorry for the delay on your solution getting posted. My blog waits for approval to display posts from new people.)
LikeLike
Did my solution get lost? 😦
LikeLike