Explore BrainMass

Algorithm to detect single bad coin using pan balance

Eight coins are identical in appearance, but one coin is either heavier or lighter than the others, which all weigh the same.

Describe an algorithm that identifies the bad coin in at most three weighings and also determines whether it is heavier or lighter than the others, using only a pan balance.

Solution Preview

The algorithm description below has been interspersed with pseudo code, apart from the logic explaining hows and whys behind working of this algorithm.

Notation "W(X)" in the description indicates the weight of coins in set X.
Initially, the coins are labelled as C1, C2, C3, C4, C5, C6, C7 and C8.

1. Divide the given 8 coins into 3 sets of size (3,3,2) coins respectively i.e.

S1 = {C1, C2, C3}
S2 = {C4, C5, C6}
S3 = {C7, C8}

if (W(S1) == W(S2)) {
The bad coin is either C7 or C8. Go to step 2 to find it.
} else {
The bad coin is one of {C1,...,C6}. Go to step 3 to find it.

2. Since the coins in sets S1 and S2 i.e. {C1,..,C6} are of right weight, we pick up any coin from either of these two sets and refer to it as R.

if (W({C7}) != W({R})) {
C7 is the bad coin. It's weight relationship with R
determines whether it is heavier or lighter.

} else {
C8 is the bad coin. We ...

Solution Summary

Solution describes an algorithm to detect the single bad coin, interspersed with pseudo code, analysis and detailed explanations on hows and whys behind correct working of this algorithm.