Monday, June 18, 2007

Going Old School

If I'm going to do this puzzle thing, maybe I should start with the classics. You know, the puzzles that everyone has seen before, but maybe not everyone remembers how to solve. And then I can explain the solution. Heck, I can run off three or four of those this week, and maybe I'll be inspired to come up with better material.
So here goes: A coin collector has a case containing eight Spanish Doubloons, one of which is counterfeit. The coins look and feel identical, but the replica is slightly lighter than the other seven coins. The collector challenges you to find the fake coin, using only an old-fashioned balancing scale (the kind with two plates: you put something on one plate, you put something on the other, it tells you which is heavier), in as few weighings as possible. What is the minimum number of weighings needed to determine the fake?


anne57 said...

Without too much thought, here's my guess: 1. put 4 on each side, discard heavier side. 2. of remaining 4, put 2 on each side, discard heavier pair. 3. Put one of the remaining pair on each side, the lighter one is the replica. So that's 3 weighings.

Leo said...

You know, these questions kinda give me LSAT flashbacks.

J. Bowman said...

The important part of this problem is to recognize that there are three possible results from putting two coins on the scale: coin A could be heavier, coin B could be heavier, or the two coins could balance. If we have only three coins, putting two coins on the scale allows us to identify the fake by placing one coin on each side of the scale (if they balance, the third one is the fake). Similarly, it only takes two weighings to find the fake among nine coins, by breaking them up into three groups of three (if you have eight coins, you can use two groups of three and a group of two).
In fact, you can get up to 3^n coins with n weighings.
Incidentally, 8 is the optimum number to use in this problem if you are being tricky; because it is a power of 2, solvers are naturally led to a solution using three weighings. If you want to lead your solvers to the correct answer, 24 is better; the tendency is to divide by 2 until they are left with a set of three coins, and once they've figured out how to get that in a single weighing, they realize they can apply the concept earlier in the process.