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 i 8. A verbal description of the decisions to be made is:

**1.** Compare the sum of weights 1-3, *s*_{1} , and weights 4-6, *s*_{2}. There are three possibilities: *s*_{1} = *s*_{2},*s*_{1} < *s*_{2}, and *s*_{1} > *s*_{2}. If *s* _{1} = *s*_{2}, 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** *s*_{1} = *s*_{2},: 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** *s*_{1} < *s*_{2}: Now *w*[7] and *w*[8] are known to be standard. Two of the coins in the triplets forming *s*_{1} and *s*_{2} need to be isolated, and two are switched. For example, the comparison might be between s_{3} = *w*[1] + *w*[4] and s_{4} = *w*[2] + *w*[5], isolating *w*[3] and *w*[6] from the other four.

**1.2.1** s_{3}: < s_{4}: 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** s_{3} = s_{4}: Then coin 3 or coin 6 is counterfeit, and one should be tested against one of the six known standards.

**1.2.3** *s*_{1} > s_{4}: The switching of coins 2 and 4 caused the balance to shift, and so one of them is counterfeit.

**1.3** *s*_{1} > *s*_{2}: 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:

**procedure** *Compare*(*Coin1,Coin2,Standard,BadCoin,Light*)

**if** *Coin1* > *Standard*

**then** *BadCoin* *Coin1*

*Light* *FALSE*

**else** *BadCoin* *Coin2*

*Light* *TRUE*

**endif**

**end** *{Compare*

The procedure then becomes:

**procedure** *EightCoins*(*w,BadCoin,Light*)

*S1**0*

*s2**0*

**for** *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* < *s2*

**case**

*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** *{EightCoins*

Program

## Program

Program for trying it yourself

**PGV.1** Write the Eight Coins program and run it with several of the possible input sets.

Go to Section W Return to Table of Contents