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)

Every weighing gives one of three results: the pans are balanced, the right pan is heavier, the left pan is heavier. As such it provides the equivalent of a base-3 digit, and so multiplies the number of possibilities covered by 3. So the solution to part A is N = 3^X.

The specific procedure for part A is to take one third of the set of coins and place it on the first pan, and another third on the second pan. If one side goes down, you know in which of these two pans the bad coin is located. If neither side goes down, the third that wasn't weighed has the bad coin. Continue as before with the set reduced to 1/3 its size.

Part B presumably needs only one more bit of information and one additional weighing supplies even more than that (a base-3 digit rather than a base-2 digit). Based on information theory you could have N = [(X^3)/2], where the square brackets indicate the floor function, or truncated quotient. As to a specific general strategy for any X, I can't think of any.

Posted by Charlie on 2003-05-14 09:17:00