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)

(In reply to Weighty Solution (maybe!) by Chris)

I realized two things after I posted:

1) The formula does not apply for X=1. One weighting would not give us enough information to detect a fake from any number of coins.

2) There may be numbers of coin for which the equation doe not seem to hold true. For example, 19 coins cannot be detected in 5 weightings as one might suspect. Remember that the equation gives a maximum number of coins for a given number of weightings.
Since 19 is not divisible by 4, this will not be an efficient use of the scale, and therefore, not a maximum number. Indeed, one could detect a fake from 64 coins in as many weightings (six), due to symmetry. I hope this helps.

Posted by Chris on 2003-05-14 10:48:06