You are given twelve coins, 11 of which are true, and 1 of which is a counterfeit. You are told that the counterfeit, or false, coin may either be heavier or lighter than the real coins. You are given a balance scale and are asked to determine, within three weighings, which of the twelve coins is the counterfeit and whether it is heavier or lighter than a true coin.
I've experimented with the display of this problem. I don't know if it will be clear. I've never liked the verbal discriptions of what to do and I wanted to see if a state diagram might be easier to follow. I'm hoping this will be more clear to the reader who hasn't already tried to solve the problem, but the problem is that my notation is still not as clear as I would like it to be. It takes almost as much effort to figure out the notation as it does just to read the text solution. Oh, well.
The coins are labelled initially as {a - j}. The lower case indicates that no information is known about the coin. Once a coin is known to be true it is labelled with the same letter, only upper case. So, once we know that 'a' is true, we label it 'A'. If it is known that a coin cannot be light, then we append a '+' to it, while a '-' is appended if it is known that the coin cannot be heavy.
Only false coins appear on terminal nodes (end states) and a plus or minus in this state means that the coin is either heavy or light, respectively.
Each node (state) is labelled with a number, except for terminal nodes (end states) which are not labelled, but present the determination of the sequence of weighings that led to that terminal node.
(Typing this in was pretty tedious. If it appears I've gotten confused, please alert me to the possibility.)
Note that each transition is labelled with a plus, minus, or equal sign; that is, the link (the arrow) from each node to the next on the graph has a '+', '-', or '=' next to it. This is the transition condition -- the input that causes the transition between the states. These symbols denote whether the LEFT side of the scale is heavier than the RIGHT side of the scale:
+ : left heavier than right.
- : left lighter than right.
= : left balances right.
To help you read the state diagram, here's a partial interpretation
of state 0.
Start with state 0.
If the coins balance we know that none of {A-H} are counterfeit,
and follow the '=' transition to state 1.
If the left column of numbers is heavier than the right, we denote
this as a 'plus' condition and follow that link. We note that this
single measurement (at state 0) has given us 3 facts:
i. {a-d} are not light counterfeits, and are denoted 'a+' thru 'd+'.
ii. {e-h} are not heavy counterfeits, and are denoted 'e-' thru 'h-'.
iii. {I-J} are not counterfeits.
i- k+
^ ^
-\ /+
\ /
3
i- E _____> j-
k+ F = l+
^ ^
-| /
0 | /+
a e 1 /
b f = i k = 2 -
c g -------------------------> j E --------> l E ---> l-
d h \
|\ \____________
| \ + \
| \ |
+| \- _____> h+ V
| \ 6 =/ 4
| \____> a- c- = 7 / + i+ E =
V b- d- ---> g+ f+ ----> g+ k- F -----> j+
5 e+ J \ |\___
a+ c+ -|\+ -\_____> f+ -| \+
b+ d+ | \________ V V
e- J | \ k- i+
|\ \_______ +------+ \_______
+| \_______ \ |_____ \
| - \ \= \ \_______________
V \ \_____ V \
8 \ \ 11 + V
a+ J ---> b+ \ \ a- J ---> b- 12
| V \ \ d- J
+| 9 V -\_____> a- e+ K
V d+ J 10 + /|\
a+ e- K g- f- ---> f- / | \
/|\ |\ / | \
/ | \ =| \- +/ =| \-
-/ =| \+ V V V V V
V V V h- g- e+ c- d-
e- c+ d+
You're probably wondering why I didn't use '<' and '>' instead of '-' and
'+' to denote state transitions. Well, I tried it (because it does make
more sense), but it makes the diagram harder to read. I really like this
symmetry of the solution, and that's why I like the state diagram, because
it makes that symmetry a little more obvious.