Twelve Coins
My grandpa gave me this problem over the phone recently:
Given a balance and twelve coins, one of which is a different weight from the others, determine which coin is different and whether it is light or heavy.
My instinct was to play around with different weighings and see what information could be learned. Perhaps I could stumble onto the correct answer.
After thirty minutes or so, I was stuck. So I tried working from first principles. Clearly, only weighing the same number of coin on each side would convey any information. This meant the starting configuration must be one of (1,1) (2,2) (3,3) (4,4) (5,5) (6,6). If the scale was balanced, then the non-weighed pile must contain the offender (there is only one offender, so it is not possible to have two piies of equal counts weigh the same with the offender). If the scale was unbalanced, the offender must have been weighed.
If there were only three coins, the problem could always be solved in two weighing from this information alone. One coin would always be identified as a normal or offending coin, and could be swapped with a weighed coin to infer the missing parameter. Four coins would require three weighings - two to determine the coin and one to determine the weight.
... unfortunately this did not immediately clarify anything for me. I needed to bridge the gap from a starting configuration to a scenario I could solve in two moves.
So, several colored markers later, I finally figured out the solution.
The key hurdle to overcome is the urge to make piles of even numbers. Ideally, piles are put in sets of three or one so that a subsequent weighing can always determine a feature of the set. It is also important to recognize that information (postive and negative inferences) from subsequent weighings can be chained together to make inferences (i.e. get more information).
Suppose the first weighing is
1 5 9
2 6 10
3 7 11
4 8 12
/
---
/ ^
The offender has been weighed, and we need to efficiently eliminate candidates. We can infer the weight of the offender if we can identify the number (as once the number is found, this first weighing implies heaviness or lightness). Switching half of the pairs will not work in two moves. Instead, we can split the coins like so
1 2 7
3 4 8
5 6
/
---
/ ^
Had the weighing been even, we just weigh 7 against any coin but 8 and infer the rest. Otherwise, we have three candidates, and the next weighing will be
1 3 2
/
---
/ ^
Suppose the first weighing is
1 5 9
2 6 10
3 7 11
4 8 12
_______
^
This implies the offender is in the unweighed pile, and the first eight coints are normal. The next weighing must establish either the offender or the weight. But, we can see that something like
9 5 9
10 6 10
11 7 11
12 8 12
/
---
/ ^
leaves us to separate four coins in one weighing (not possible). We may get more utility out of our measurement by weighing two candidates against two others.
9 10
11 12
/
---
/ ^
But now there is no guarantee of identifying the coin
Thus, we must make the counterintuitive approach of splitting the candidates up unevenly
9 1 12
10 2
11 3
/
---
/ ^
After the fact, I did some further research on the problem.
StackExchange Mathed.org av8n.comOther intersting variations of the question include:
Additional 'odd' coins
Additional balances