   Even harder coin problem In three weighings there are 27 possible outcomes (3 * 3 * 3).  One possibility (all balanced) is not useful to us since we are trying to identify a single odd coin.  This leaves 26 useful results, or 13 pairs of opposite results. (For example, RRB is the opposite of LLB.) Since we want to know which coin is odd (1 in 12) and how it is odd (heavier, lighter) it is necessary to consider the results as pairs of opposites, with one pair indicating the coin, and which form indicating whether it's lighter or heavier. Since there are 24 actual possibilities (1 of 12 coins, light or heavy), I have enough weighing results to cover all coins.  All we need to do now is determine a proper ordering of the expected results which will map to a possible weighing. It turns out we need to weigh 8 coins at a time, 4 on each side.  So once we determine the combinations of weighing results, we must order them so any one weighing (first, second or third) has a particular result exactly 4 times.  (eg. for 12 outcomes, I can have the first weighing be LEFT in exactly 4 of the outcomes.) Here is the table I came up with of the 27 possible outcomes, paired with their opposites and ordered as necessary to be useful for the problem: Weighing  Opposite  Coin (see below) A B C    A B C --------  --------  ---------------- B B R  -  B B L        1 B R B  -  B L B        2 B L R  -  B R L        3 B L L  -  B R R        4 L B R  -  R B L        5 L B L  -  R B R        6 L R B  -  R L B        7 L B B  -  R B B        8 R L R  -  L R L        9 R R L  -  L L R      10 R L L  -  L R R      11 R R B  -  R R L      12 R R R - L L L -> leave out, for balance B B B={not useful} Notice that in each column (representing one weighing) there are 4 L's, 4 R's and 4 B's.  L's are LEFT, R's are RIGHT, and B's are BALANCED. For each triplet of weighing results we get to choose one outcome.  But the outcome we "assign" to a HEAVY weighing result determines the outcome which must be assigned to a LIGHT weighing result for the same coin.  So if BBR is the HEAVY result for COIN 1, then BBL must be the LIGHT weighing result for COIN 1.  With this table ordered thusly, we can arbitrarily assign the coins to the 12 result pairs (which I went ahead and did in the above table). This then determines the weighing order. I will arbitrarily decide that the left column of triplets indicates the odd coin is heavy and the right column indicates the odd coin is light.  So coins 1, 2 and 8 are present in only 1 weighing. Coins 3, 4, 5, 6, and 7 are present in 2 weighings; and coins 9, 10, 11, and 12 are present in all three weighings. All that's left is to translate the above map into the weighings we will request.  Since the left column is the HEAVY result, I can see that coins 5-8 must be on the LEFT in the first weighing.  Likewise, 9-12 must be on the right in the first weighing.  I continue mapping like this for each column above and get this arrangement of weighings: Weighing A:     Left:  5 6 7 8     Right: 9 10 11 12   Weighing B:     Left:  3 4 9 11     Right: 2 7 10 12   Weighing C:     Left:  4 6 10 11     Right: 1 3 5 9   By getting the results from these three weighings and comparing to the above table, I can determine the odd coin and whether it's heavier or lighter. For example, a weighing result of LRR indicates that 11 is the odd coin and it is LIGHTER.  RLL indicates that 11 is odd and HEAVIER.  BRB means 2 is HEAVY.  RBR means 6 is LIGHT.  And so on.  Because I omitted RRR and LLL, these results should never appear. This was a tough problem.  It took me about 5 minutes to determine that it was possible, and then about an hour to arrange everything so it worked and write up the results. Phil Hord Monday, October 28, 2002 Hi ! It took me a lot of time to prove that there exists a solution..., and then the same approach to solving it was followed - essentially start backwards with the outcomes and how the outcomes would result and then see if that can be forced. It is still a nice exercise to come up with a formula for number of weighings needed for N coins (The BBB outcome can actually be used if N is odd) There are altogether 27 outcomes to the weighings since each of the three weighings can be either Left Tilt, Right Tilt or Balanced (LRB) the outcomes are LLL RRR LLB RRB LLR RRL LBL RBR LBB RBB LBR RBL LRL RLR LRB RLB LRR RLL BLL BRR BLB BRB BLR BRL BBL BBR BBB Notice that withe exception of BBB they are paired up such that the L and R when exchanged give the other member of the pair. Now we can arbitarily number our coins from 1 to 12 and assign each of these numbers to the outcomes. LLL RRR 1 LLB RRB 2 LLR RRL 3 LBL RBR 4 LBB RBB 5 LBR RBL 6 LRL RLR 7 LRB RLB 8 LRR RLL 9 BLL BRR 10 BLB BRB 11 BLR BRL 12 BBL BBR unused BBB unused Now just think of where the defective coin should be in a weighing so as to case the given outcomes. One outcome is for if the coin is heavy and the other for if it is light. Now you are allowed to choose either the left outcome or the right outcome and place the numbers for their positions in the balancing, you can just follow a dynamic allocation procedure and make corrections as you go on. (LLL) RRR 1 LLB (RRB) 2 (LLR) RRL 3 LBL (RBR) 4 RBB (LBB) 5 (RBL) LBR 6 (RLR) LRL 7 RLB (LRB) 8 LRR RLL BLL (BRR) 9 (BLB) BRB 10 BLR (BRL) 11 (BBL) BBR 12 BBB In the process i was forced to drop the LRR RLL outcomes in favor of another because it was not possible to balance the Left and right hand sides with it. 1,3,5,8 + 2,4,6,7 1,3,7,10 + 2,8,9,11 1,6,11,12 + 3,4,7,9 Q.E.D. - Shyamal Shyamal L, Bangalore, India L. Shyamal Tuesday, November 19, 2002 Recent Topics Fog Creek Home