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?

(In reply to General Solution by Sanjay)

I realize that since the problem only asks us to determine the identity of the 'fake' coin and not the nature of its 'fakeness' it will be possible to 'solve' more than (3^X-3)/2 coins in X weighings.

Not having to identify the nature of fakeness allows us to leave one coin out of the weighings altogether. Hence we can 'solve' at least one more than (3^X-3)/2 coins in X weighings. However, I can't say for certain whether this is the maximum we can 'solve'.

Posted by Sanjay on 2003-05-22 05:50:21