The classical problem of eliminating a false coin out of 12 given can be solved using three steps of weighing by a simple level-balance, even without prior knowledge of the false coin being heavier or lighter than the standard coins.

Solve the same problem for 13 coins (i.e. 12 normal, one false , 3 steps to establish which is the different one and whether it is lighter or heavier), provided you may use a balance-scale with non-equal arms.

First off, there are 13*2 = 26 possibilities for which coin is lighter/heavier.  Each weighing has 3 possible outcomes <,>,= so 3 weighings gives 3^3=27 possible outcomes as an upper bound.  So it may in theory be possible to do this.

Mine is an almost solution because it while it can differentiate one false coin among 13.  But there is one possible coin (#13) whose light.heavy status is not found if it is indeed the fake.

I also use equal arms.

Number the coins 1,2,3,4,5,6,7,8,9,10,11,12,13

First weighing (1,2,3,4) v (5,6,7,8)

Case 1.  Balanced (its one of 9,10,11,12,13)

Second weighing (1,2,3) v (9,10,11)

Case 1a. Balanced (its 12 or 13)

Third weighing (1) v (12)
If its balanced we know its [13]*
If not we know its [12]

Case 1b. Unbalanced either way we know its one of (9,10,11) and whether its heavy or light.

Third weighing (9) v (10)
If its balanced we know its [11]
If not we know from the way it tips whether its [9] or [10]

Case 2.   Unbalanced we know its one of (1,2,3,4,5,6,7,8) but not wheter its heavy or light.  Consider the subcase where (1,2,3,4)>(5,6,7,8) and realize the other inequality works the same way replacing the word light with heavy.

Second weighing (1,7,X) v (2,5,6)
note: the left pan has one possibly heavy coin (1) and one possibly light coin (7) the right pan has one possibly heavy coin (2) and two possibly light coins (5 and 6) coin X is any known fair coin (9,10,11,12, or 13), three coins (3, 4 and 8) have been removed.

Case 2a.  Balanced.  Either 3 or 4 is heavy or 8 is light.

Third weighing (3) v (4)
If balanced its [8] otherwise its either [3] or [4] whichever is heavier.

Case 2b.  The left pan is heavier.  Either 1 is heavy or 5 or 6 are light.

Third weighing (5) v (6)
If balanced its [1] otherwise it is either [5] or [6] whichever is lighter.

Case 2c.  The right pan is heavier.  This means either 2 is heavy or 7 is light since only they switched sides.

Third weighing (2) v (X) where X is not 7.
Either the [2] will be shown heavy or the pans will balance meaning its [7]

Posted by Jer on 2011-02-17 18:16:48