   More Difficult coin problem Can anyone share some insight on the variation of the coin problem where you don't know if the counterfit coin is heavier or lighter and still need to do it in 3 weighs? It is keeping me up at night! :') Thank You Sal Sal DiStefano Monday, June 9, 2003 Binyomin Monday, June 9, 2003 I believe the original questioner was asking about  http://www.techinterview.org/Puzzles/fog0000000090.html There are 12 coins, there are 3 weighings, and they are non adaptive weighings. If you look at each weighing as a trinary digit, you have 27 possible permutations (Left Tilt, Balanced, Right Tilt). Since 1 coin is either lighter or heavier, there are 24 possiblities (1H, 1L, 2H, etc) needing to be represented by 27 possible numbers (LLL, LLB, LLR, LBL, etc). Make a table of the possible outcomes of weighing. If, for example, you have 2L:BBL, 2H:BBR, then coin 2 is omitted from weighings 1 and 2, and its on the right scale for weighing 3. This should head you in a direction where you can solve this problem. Peter Lorenzen Wednesday, June 18, 2003 famous 12 coin problem... Divide the 12 coins into 3 groups of 4 coins, and then divide each of the 4 coin groups into a single coin and a pile of 3 coins. Place the 3 coin piles into paper bags (for easy handling - the weight of the bags will be the same for coins on both pans, so will not affect the weighing results in any way). Place one 4 coin group on each pan of the balance, and the third one on the table. Observe the condition of the balance. This is the first weighing. Rotate the bags of 3 coins, moving the one from the right pan to the table, the one from the left pan to the right pan and the one from the table onto the left pan. Observe the condition of the balance. If it changes, it will identify the bag of 3 coins that has the odd coin and its relative weight. This is the second weighing. In that case, you have 3 coins one of which is known to be heavier (or lighter). Clear the balance and use simple logic  to identify the odd coin. That would be the third weighing. If the condition of the balance does not change, the odd coin is one of the single coins and can be identified and its relative weight determined by rotating them as with the bags of 3. That would be the third weighing. Problem solved - with no labeling, and not really much of a problem with this method. s.rajeshwar Tuesday, July 8, 2003 s.rajeshwar, Clever and succinct solution for finding the counterfeit coin, and labeling it as heavy or light, but it is an adaptive solution.  I.e. the choice of which coins to use on the third weighing depends on the results of the previous weighings.  This doesn't meet the problem requirements. However, I think with a slight alteration, it can. In essence, you divided up the coins into 3 sets with 4 coins each.  But you also divided them up into 4 sets with 3 coins each - (3 sets are  in bags, and the fourth set is the 3 loose coins). In the first two weighings, you identified which set of 3 coins contained the odd coin.  Also, if the odd coin was in a bag, you identified whether it was too heavy or too light.  If the odd coin was loose (unbagged), then you learned that it was either one coin being too light, the other being too heavy, or the third (only unweighed coin) being odd. For the third weighing, put one coin from each bag together with the unweighed loose coin on the left, and one other coin from each bag and one other loose coin (pick one, doesn't matter whch) on the right.  Now you can name the odd coin, and whether it is light or heavy.  Furthermore, we've decided ahead of time exactly which coins to weigh on the left and right in each weighing ahead of time. luv2puz Tuesday, July 15, 2003 Peter's answer is correct. Considering that there are 24 possible scenarios, 12 coins (each could be heavier or lighter), and 3 weighings with 3 possible outcomes each (heavy, light, same) we have 27 possibilities. It only remains to map the 24 outcomes to 24 of these possiblilities in such a way that the scale is balanced in the number of coins on both sides. This is non-trivial and there are many maps possible. If you want details on a particular mapping, feel free to email me and I can provide you with a non-adaptive solution. Anurag Jain Wednesday, August 27, 2003 Recent Topics Fog Creek Home