Solve the 12-Coin Problem with 3 Weighings

[mdelisio]

This is a classic. Forgive me if this has been posted before.

You have 12 coins, and you know that one one of the coins may be fake. You also know that a fake coin will not have the same weight as a good coin: it will either be heavier or lighter. You have at your disposal a balance scale. This scale will only tell you if the weight of the items in the left side are heavier, lighter, or equal to the weight items in the right side.

Devise a method to determine which coin (if any) is bad and if the bad coin is heavy or light using only three scale measurements.

 

[denverdoc]

I believe this is a decimation by groups of three problem, and shooting from the hip, the first eight are tested by weighing 4 on each pan: either they balance or they dont. either way you have a reference pile, and from that can conclude which one is odd by extending the same logic in the next two weighings.

Edit, dumb mistake, that would be weigh 3 vs 3, need to divide set by 1/2. By noting the direction the balance tips, and using group of 3 known goods on one side, it is possible to determine which of the 4 sets of 3 contains the bad coin. Then 2 of the three are taken at random from the bad set. If these balance, third one is off. Otherwise the direction of the tip plus the direction of previous tips ID's the off. [/color]

 

[Rogerio]

I believe this is a decimation by groups of three problem, and shooting from the hip, the first eight are tested by weighing 4 on each pan: either they balance or they dont. either way you have a reference pile, and from that can conclude which one is odd by extending the same logic in the next two weighings.

Edit, dumb mistake, that would be weigh 3 vs 3, need to divide set by 1/2. By noting the direction the balance tips, and using group of 3 known goods on one side, it is possible to determine which of the 4 sets of 3 contains the bad coin. Then 2 of the three are taken at random from the bad set. If these balance, third one is off. Otherwise the direction of the tip plus the direction of previous tips ID's the off.

I think it doesn't work. If the first 6 coins are good, you have only 2 measurements to determine which from the 6 remaining coins is the fake one.

 

[Rogerio]

What about 4 vs 4 ?

 

[denverdoc]

I think it doesn't work. If the first 6 coins are good, you have only 2 measurements to determine which from the 6 remaining coins is the fake one.

I thought I considered the null/null/swing sequence, but now can't recall how I differentiated the light from the heavy since you have no prior swings. Hmmm need to rethink this one.

 

[vamfun]

I agree that it is a groups of three problem as described by denverdoc. Extending mathmatically we can state the problem solution for any number of coins:

n= number of coins
w= number of weighings required

find minimum w such that 3 exp (w) >= n note: 3 exp(w) is 3 to the power of w.

1<= n <=3 w=1
4<= n <= 9 w=2
10<= n <= 27 w=3 This is solution for 12
28<= n <= 81 w=4
etc

 

[grant9076]

I didn't look closely at this one until a couple of hours ago. This is a good one. Anyway, I think that this is the solution.
Divide into 3 groups of 4 coins.

Weigh 1st group against 2nd group for first measurement.
If scale does not tip, then 3rd group is bad (more on that later).
If scale tips, then:
Swap 1 coin in heavy group with 1 in light group, remove 2 from heavy group and put aside and replace them with 1 good coin from third group, remove 1 from light group. There should now be 3 coins on each side of the balance.


Then take 2nd Measurement.
If scale tips the other way, then one of the swapped coins is bad. Take the heavier of the 2 coins and measure against a good coin. If it balances, then the light coin is bad. If it is heavier then it is too heavy.

If the scale stays tipped in the original direction, then either one of the 2 coins which stayed on the light side is too light, or the one which stayed on the heavy side is too heavy. Measure the 2 which stayed on the light side against each other. The lighter one is the counterfeit. If they are balanced, then the one which stayed on the heavy side is too heavy.

If the scale is balanced after the 2nd measurement, then either one of the 2 which were put aside from the original heavy side are too heavy, or the 1 put away from the light side is too light. Measure the heavy coins against each other and the heavier is the counterfeit. If balanced then the one which stayed on the light side is too light.



If the bad coin is in the third group (as mentioned above), then do the following:
Split the last 4 into 2 groups, and the replace one of the coins in one of these groups with a good coin. There should be 2 coins on each side.


Take the 2nd measurement.
If the scale balances then the coin that was replaced was the bad coin. Measure (3rd measurement) this against a good coin to see if it is too heavy or light.

If the scale tips then measure the 2 suspected coins that were on the same side against each other. If they were on the heavy side, then the heavier one is bad, if they were on the lighter side then the lighter one is bad.
If they balance but were on the heavier side, then the suspect coin that was with the good coin is too light. If they balance but were on the light side then the suspect coin that was with the good coin is too heavy.

 

[Rogerio]

.
.
.
Extending mathmatically we can state the problem solution for any number of coins:
n= number of coins
w= number of weighings required

find minimum w such that 3 exp (w) >= n note: 3 exp(w) is 3 to the power of w.
.
.
.
10<= n <= 27 w=3 This is solution for 12.
.

If this was right, then w=3 would be solution for n=13 too.
But it is not...:-(

 

[vamfun]

You're right!
Correction: The above assumed that one coin was heavy. This is acutally unknown , so an additional weighing is necessary against known good coins for many of the cases (excluding n=10,11 and 12 at least) Sorry

 

[SGT]

I agree that it is a groups of three problem as described by denverdoc. Extending mathmatically we can state the problem solution for any number of coins:

n= number of coins
w= number of weighings required

find minimum w such that 3 exp (w) >= n note: 3 exp(w) is 3 to the power of w.

1<= n <=3 w=1
4<= n <= 9 w=2
10<= n <= 27 w=3 This is solution for 12
28<= n <= 81 w=4
etc

It does not work for n = 2 or n = 3.
If the balance tips, you don´t know if the fake is lighter or heavier than the true.

 

[Rogerio]

Ahh...but it is. Try dividing into piles of 3 3 and 4. First, weigh the 3 and 3 piles. If one is heavier then it only takes 1 more weighing.
.
.
.

Then tell me how!
Remeber "the fake coin will either be heavier or lighter"...:-)

As I told you before, if there are 13 coins you will need (sometimes) more than 3 weighings to determine the fake one.

 

[Gokul43201]

Sorry for the intrusion, but...

Holy cow, Rogerio! Looong time, no see.

 

[Rogerio]

Holy cow, Rogerio! Looong time, no see.

Hi Gokul! Nice to see you!

Well...I'm back!
:-)

 

[vamfun]

Ok, I am with you now. If a coin is either light or heavy then an additional weighing is needed against the reference coins for most of the cases (excluding n=10,11 and 12) I will update the table when I get a chance.
Sorry for the confusion.

PS I had worked this problem before when the coin given as heavier...and read this into the problem rather than answering the right question... seems to be a bad habit of mine:)
update:
The new table would look like this:
n= number of coins
w= number of weighings required


n=1,2 no solution
n=3 w=2
4<= n <= 12 w=3

for n> 12 find minimum w such that 3 exp (w-1) >= n
note: 3 exp(w-1) is 3 to the power of (w-1).

this gives
13<=n<=27 w=4
28<=n<=81 w=5 etc

can anyone find some holes in this one?

 

[Craigh00000]

Ok, this one is easy. Take the scale to the local scientist. Tell him you will give him the scale if he will tell which coin is fake. Let him do the math while you have a drink with the local lady of the evening biggrin: