Given a balance scale that is sure to break after X weighings, find an equation for the largest number of coins N, from which you can determine a fake coin that has the wrong weight if

A: You know whether the fake is lighter or heavier

B: You do not know whether the fake is lighter or heavier

(Assume only one of the N coins is fake)

For part A, I agree with Brian and Charlie about the equation being N = 3^X coins and with the procedure they described.

For part B, however, I disagree. Actually, using Charlie's statement that an extra weighting will provide us with a little more information and the fact that we don't have to know how the coin is fake (light/heavy), I came up with:

N = 2^X coins maximum with X weightings.

The procedure is as follows:
Divide the coins into four groups which we will label A,B,C and D. First weigh group A against group B. Then weigh group B against group C. These two weightings will give one of four results (I will use <> for 'doesn't balance'):

A=B=C: Then group D has the fake.
A=B<>C: Then group C has the fake.
A<>B=C: Then group A has the fake.
A<>B<>C: Then group B has the fake.

In each case, repeat the process with the group indicated, discarding as real the three other groups. This will continue until the groups have only one coin each and one coin is indicated as the fake.

Posted by Chris on 2003-05-14 10:30:45