You know that one of twelve coins is counterfeit and you know that it is either a little bit heavier or a little bit lighter than a genuine coin. Using a balance scale that tells you which side of the scale is heavier, identify the counterfeit coin and determine whether it is heavier or lighter than a genuine coin in 3 weighings.
The solution that I describe goes like this: 4 vs 4, 3 vs 3, 1 vs 1. (The numbers are the numbers of coins weighed against each other.) The first solution I came up with went like this: 4 vs 4, 5 vs 5, 2 vs 2.
There is a solution that goes: 4 vs 4, 4 vs 4, 4 vs 4 and interestingly it also meets an additional constraint of not needing to adjust which coins are weighed based on the previous weighings.
Really? So soon? I thought about it for a month! Then I woke up with an answer. A solution is below, but read on at your own risk. A late "Aha!" is a lot more fun than an early "Oh."
E = Equal (known)
H = Heavy (possibly)
L = Light (possibly)
(1) Weigh 4 vs 4. If they are equal (E), then you know that the counterfeit coin is one of the 4 that you didn’t weigh. Go to step (2). If they are not equal, go to step (5).
(2) Weigh 3 of the possibly counterfeit coins against 3 genuine coins. If they are equal, then you know that the fake coin is the one coin that you have not yet weighed. Go to step (3). If they are not equal, then they are either heavier or lighter than the 3 genuine coins. Go to step (4).
(3) Weigh the counterfeit against a genuine coin to determine whether it is heavier or lighter than a genuine coin.
(4) If the 3 suspicious coins are heavier than the 3 genuine coins, then you know that the fake coin is heavier than a genuine coin; if they are lighter, then you know that it’s lighter. If they are heavier (or lighter), then weigh one of the suspicious coins against another suspicious coin. If they are equal, then you know that the coin that you didn’t weigh is counterfeit and heavy (or light). If they are not equal, then the scale will tell you which coin is counterfeit and heavy (or light).
(5) If after the first weighing you get this result: HHHH vs LLLL, then you know that the counterfeit coin is either one of these 4 and heavy or one of those 4 and light. Use your second weighing to weigh HHL vs HHL. If they are equal, then you know that the counterfeit coin is one of the 2 L’s that you didn’t put on the scale for the second weighing. Go to step (6). If one of the HHLs is heavier than the other HHL, then you know that it is either one of the Hs that is making the heavy side heavy or it is the L on the other side that is making the light side light. Go to step (7).
(6) Weigh the two Ls against each other to see which one is counterfeit and light.
(7) Weigh the two Hs from the heavy HHL side against each other. If one of them is heavier than the other, then that coin is the counterfeit coin and heavy. If they are equal, then the L coin from the light HHL side is the counterfeit coin and is light.
There are other solutions to this problem. And some are interestingly different. For example, there is a solution whose second and third weighings do not depend on the outcome of any of the previous weighings.