If you haven't done any of the other coin problems, then you might want to go back and try those now, this one is very difficult, even if you have figured out the other ones.

This time, as the title implies, there are 39 coins, and one is fake. You have a balance scale, which can be used 4 times.

How would you find the fake coin?

3 likely results per weighing; Left heavy (L), Right heavy (R), Balanced (B). Hence, 3^X likely results for X weighings.

Create X rows, 1 to X. For row n repeat 'L','B', &'R' 3^(n-1) times each, then repeat the pattern 3^(X-n) times. Full table for X=3:

Row 1: L,B,R,L,B,R,L,B,R,L,B,R,L,B,R,L,B,R,L,B,R,L,B,R,L,B,R
Row 2: L,L,L,B,B,B,R,R,R,L,L,L,B,B,B,R,R,R,L,L,L,B,B,B,R,R,R
Row 3: L,L,L,L,L,L,L,L,L,B,B,B,B,B,B,B,B,B,R,R,R,R,R,R,R,R,R

Each column is a possible result of X weighings. Weighing strategy:

Column 1 to (3^X-3)/2 represent coins with matching numbers. L,B,& R in row n tell us where coins go during nth weighing. L=Left; R=Right; B=Break (or stay out). A minor adjustment. First place coins as per table, then remove all known 'good' coins from Left & add enough 'good' coins to Right to make equal coins on both sides. There will always be enough 'good' coins.

For X=3, 1st weighing: 1,4,7,10 on Left; 3,6,9,12 on Right; 2,5,8,11 on Break. If Left heavy, then 2,5,8,11 are 'good'. So in the second weighing first put 1,2,3,10,11,12 on Left & 7,8,9 on Right, then remove 2 & 11 from Left & add one 'good' coin to Right. So on. After X weighings, match results with one of the columns.

If match is in the first (3^X-3)/2 columns, 'fake' coin is heavy & its number equals the matching column. If match is in the last (3^X-3)/2 columns, 'fake' coin is light & its number equals 3^X+1 minus the matching column. Three central columns are always 'impossible' results. (3^X-3)/2 is maximum 'solvable' in X weighings.

Posted by Sanjay on 2003-05-16 13:16:12