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)

A. N = 3^X

As everyone here has already said, each weighing has 3 possible results, so N weighings has 3^X possible results. Succesive trifurcation of the 'found out' bunch does the trick. Each succesive weighing narrows the field by 2/3rds and it takes X weighings to reduce the possibility to 1 starting from 3^X.

B. (3^X-3)/2

If the the type of 'fakeness' is not known then it doubles the information need and yields three less real possibilities than the theretical possibilities. This is because most known strategies involve some switching of coins from one side to the other. This leads to three 'impossible' sequences where a result from a later weighing contradicts a result from an earlier weighing.

Posted by Sanjay on 2003-05-16 16:31:42