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! :')
Monday, June 9, 2003
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.
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
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
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
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
Problem solved - with no labeling, and not really much
of a problem with this method.
Tuesday, July 8, 2003
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.
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.
Wednesday, August 27, 2003
Fog Creek Home