require number of weighings

Question

12 coins look the same but one of them is heavier.  what is the minimum number of weighings require to find the counterfeit coin? 

Answer 1

This is a classic problem (solution below by Edwin McCravy).

 

What most people forget is that a balance scale has three possible results (left heavy, balanced, left light).  In computer architecture, this is also how a compare operation produces a result (when two values are subtracted, the result is negative, zero, or positive [that is, less than, equal, greater than]).

 

So, if you use the information that there are 3 results to each weighing, you can start with 12 coins, weigh 3 times, and always know which coin is different and whether it is heavier or lighter.

 

(note: This is much better understood using computer animation; but you can get 11 of the same coin and 1 different and practice each of the cases.)

 

 

- - - - -

 

Weigh any 4 with any other 4.
`
Case 1. This first weighing (4 with 4) balances.
`
Then the 8 coins that you weighed are all good and the 4 that you didn't weigh are suspects for the fake coin.
`
Weigh 3 good coins against 3 suspect coins.
`
A. If they balance then the remaining suspect coin is the fake coin, so then you weigh the fake coin with one of the good coins to see whether its heavier or lighter.
`
B. If they don't balance then you can tell whether the suspect coin is heavier or lighter, so weigh one suspect coin with another. If they weigh the same, the remaining one is the fake one, and if they don't, you know which of the two on the scale is the fake one because you already know whether it's heavier or lighter.
`
Case 2. The first weighing 4 with 4 doesn't balance. Then put two from the heavier side and one from the lighter side on each side of the scale.
`
A. If they balance then you know the fake coin is one of the two from the previous lighter side that you didn't weigh, and you also know that the fake coin is lighter. So weigh one of those with a good coin. If those balance then you know the one you didn't weigh is the fake coin and you know it's lighter. If they don't balance, then the lighter one on the scale is the fake one.
`
B. If they don't balance, then the fake coin is either one of the ones on the PRESENT heavy side from the PREVIOUS heavy side and it's heavier, or you know that the fake coin is one from the PRESENT lighter side from the PREVIOUS lighter side and it's lighter. Now from the PRESENT heavy side, weigh one from the PREVIOUS heavy side with the other from the PREVIOUS heavy side. If they weigh the same, then the fake coin is the one from the PREVIOUS lighter side and it's lighter. Otherwise the heavier one from the PREVIOUS heavier side is the fake coin and it's heavier.

Answer 2

Hi Ximena.

 

Break the 12 coins up into 4 groups of 3 coins, so that you have:

 

Set 1

Set 2

Set 3

Set 4

 

Each set contains 3 coins.

 

Take any two sets of three and put them both on opposite ends of the scale.

 

If they are even, you know neither of them have the heavier coin in them, so both sets can be discarded and the other two can be weighed against each other.

 

If one of the sets tilts lower, you know that set has the heavier coin, so the other set can be discarded.

 

Take your heavy set of three coins and weigh one coin versus another, keeping the third coin off the scale.

 

If the coins on the scale are even, you know that the one on the floor is heaviest. If one of the coins tilts lower on the scale on the scale, you know that one is heaviest.

 

So at a minimum, you need at least 2 weighings. This is if you're lucky and the heavy coin is in one of the first 2 sets you weighed against each other. At maximum, you need 3 weighings, assuming the first two sets did not contain your heavy coin.

 

For example...

 

Say you weigh Set 1 vs Set 2, and both sets are equal. You know that none of the 6 coins involved can be the heavy one, so you discard Set 1 and Set 2.

 

You then weigh Set 3 vs Set 4, and the coins from Set 4 tilt lower. You know now that the heavy coin rests in Set 4, so you discard Set 3.

 

You then take the three coins in Set 4 and put one on each side of the scale, leaving the third coin on the floor. You see that the coins on the scale are even, so that tells you the coin on the floor from Set 4 is your heavy coin.

 

This example shows the maximum number of times you had to weigh coins, because neither Set 1 or Set 2 had the heavy coin in it. If you had weighed Set 3 vs Set 4 first, you'd know immediately which set had a heavy coin, and thus can skip the extra weigh step, leaving you with just 2 weighings.

 

Hope this helps.