Fog Creek Software
Discussion Board




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 09, 2003

http://www.techinterview.org/Solutions/fog0000000116.html

Binyomin
Monday, June 09, 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 08, 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