In Golden Earring – Radar Love I had a big problem.
This the solution so please read the problem first and have a go at solving it yourself.
My wife has lost a golden earring, I can buy a bunch of similar earrings but I know one is a fake.
I can weigh two groups of earrings, each weighing can give one of three results: they weigh the same; the left group is heavier, the right group is heavier.
The question is – how many earrings can be in the bunch I buy and leave me confident that I can find the fake with just three weighings?
You may have noticed that ears normally come in pairs. So do earrings.
My wife still has one earring. We know this earring is good and we can use it in our weighings if that helps us.
Always try the simplest case first and see if that gives any insights.
Suppose we are not allowed any weighings, then we can cope with a bunch of one earring; as it is the only earring it must be the fake. We don’t learn if it is heavier or lighter than a genuine earring.
If we are allowed one weighing then we can cope with a bunch of two earrings. First we compare earring 1 with my wife’s other earring which we know is good.
- If they differ then earring 1 is fake and we learn if it is heavier or lighter.
- Otherwise they weigh the same and earring 2 is the fake, but we don’t learn if it is heavier or lighter.
A good approach to these sorts of problems is to think about the amount of information you can gain. One possibility is that each weighing is equal; then we know that we haven’t weighed the fake earring, the fake is the one earring we haven’t weighed. There are 26 other possible results; they must involve weighing the fake and so finding out if it is heavier or lighter than a good earring.
So the 27 possible results from three weighings will differentiate between:
an earring which is never weighed is the fake;
earring 1 is the fake and is light;
earring 1 is the fake and is heavy;
earring 2 is the fake and is light;
earring 2 is the fake and is heavy;
earring 13 is the fake and is light;
earring 13 is the fake and is heavy.
So the maximum number of earrings is 14.
We have shown that 14 is the maximum, but we haven’t shown that it is possible. Can you find a method?
Can you find a general formula for n weighings?
Always think about how much information you can gain from the remaining weighings; if you leave yourself with four earring candidates and one weighing then you have gone wrong. That’s the best clue I can give you.
I’ll answer these in the comments in the near future if no-one else gets there first.