Some problems are both well enough known and representative enough that every computer science major should work through them at some time. One of these is the Eight Coins Problem, a representative of a class of common weighing puzzles. It is this:
One of eight apparently identical coins is known to be counterfeit and hence of different weight from the other seven. An equal-arm balance is to be used to discover in three weighings which coin is different and whether it is heavier or lighter.
There are sixteen possible results: 1-Light, 1-Heavy, 2-light, . . ., 8-Heavy, and a structured approach is likely to be worth developing. A systematic approach to the determination is to form a decision tree where each node describes a weighing to be made, determined by the results discovered so far. An interior node also determines which child to use for the next decision, and a leaf node is the correct answer if reached by proper use of the tree.
Let the coins have weights w[i] for 1
1. Compare the sum of weights 1-3, s1 , and weights 4-6, s2. There are three possibilities: s1 = s2,s1 < s2, and s1 > s2. If s 1 = s2, then the counterfeit coin is isolated as the pair of coins 7 and 8, and the other six are all of standard weight. When coins 7 and 8 are compared with each other, one of them will be heavier. The other two cases use the second comparison to isolate a similar pair of coins and provide relative weight information. At the third weighing, one of the isolated pair is compared to a standard coin, and the answer becomes apparent.
1.1 s1 = s2,: The bad coin is isolated in the pair w[7] and w[8], and so they are compared to each other.
1.1.1 w[7] > w[8]: One of them, say w[7], is compared with a standard coin, say w[1].
1.1.1.1 w[7] > standard: Then w[7] is the bad coin, and it is heavy. Otherwise, w[8] is the bad coin, and it is light.
1.1.2 w[7] < w[8]: This is symmetric to 1.1.1 above.
1.2 s1 < s2: Now w[7] and w[8] are known to be standard. Two of the coins in the triplets forming s1 and s2 need to be isolated, and two are switched. For example, the comparison might be between s3 = w[1] + w[4] and s4 = w[2] + w[5], isolating w[3] and w[6] from the other four.
1.2.1 s3: < s4: Clearly coins 3 and 6 were standard, and either coin 1 is light or coin 5 is heavy because switching coins 2 and 4 left the balance tipped in the same direction. Either coin 1 or coin 5 is to be tested against a standard, because these two are now isolated as the bad pair.
1.2.2 s3 = s4: Then coin 3 or coin 6 is counterfeit, and one should be tested against one of the six known standards.
1.2.3 s1 > s4: The switching of coins 2 and 4 caused the balance to shift, and so one of them is counterfeit.
1.3 s1 > s2: This is entirely symmetric to 1.2 above.
Even with the abbreviation of the verbal description, the decisions to be made do not jump out at the reader. A tree diagram is helpful.
In Figure V.1, the notation indicates a comparison of i, . . ., j with k, . . ., l.
The tree is illustrated in Figure V.2. The design of the tree calls for a comparison of a final pair with a standard weight:
The procedure then becomes:
Program for trying it yourself
PGV.1 Write the Eight Coins program and run it with several of the possible input sets.
i 8. A verbal description of the decisions to be made is:
Figure V.1
Figure V.2
procedure Compare(Coin1,Coin2,Standard,BadCoin,Light)
if Coin1 > Standard
then BadCoin
Coin1Light
FALSEelse BadCoin
Coin2Light
TRUEendif
end {Compareprocedure EightCoins(w,BadCoin,Light)
S1
0s2
0for i = 1 to 3 do
s1
s1 + w[i]s2
s2 + w[i + 3]next i
if s1 = s2
then if w[7] > s[8]
then Compare(w[7],w[8],w[1],BadCoin,Light)
else Compare(w[8],w[7],w[1],BadCoin,Light)
endif
return
endif
if s1 > s2
then case
s3 = s4 : Compare(w[3],w[6],w[8],BadCoin,Light)
s3 > s4 : Compare(w[1],w[5],w[8],BadCoin,Light)
s3 > s4 : Compare(w[2],w[4],w[8],BadCoin,Light)
endcase
return
endif
{s1 < s2case
s3 = s4 : Compare(w[6],w[3],w[8],BadCoin,Light)
s3 > s4 : Compare(w[5],w[1],w[8],BadCoin,Light)
s3 < s4 : Compare(w[5],w[1],w[8],BadCoin,Light)
endcase
end {EightCoinsProgram