SEARCH HOME
Math CentralQuandaries & Queries

search

Question from Eden, a student:

We have 12 coins same in size and shape and also weight. But among these, one coin which has same size and shape, but not in weight and we can't know that this coin was lighter or heavier.
We must decide which coin was lighter or heavier among these 12 coins in 4 times of weighting with scale.

Hi Eden.

I'll get you started. Let's label the coins ABCDEFGHIJKL. We'll gradually replace these with *s as we discover which ones are normal.

With one weighing you can determine which half of the coins is imbalanced. Put three coins on each side of the scale, say ABC vs. DEF. If they balance, you know you have ******GHIJKL, that is, the coins you weighed are normals and can be set aside, so you have a set of 6 coins left, whether you got it to balance or not.

You can't divide six coins into four quarters, so you need to change your approach on the next step. Perhaps you can make smaller sets that will work.

Remember that you have a pool now of "normal" coins to weigh against, so you could, if you chose, pick up two unknowns and weigh them against two of the normals you learned of earlier - that way you can rule out more than if you weighed two sets of unknowns against each other.

Write back if you need more.
Stephen La Rocque.

 

Hello,
We must be careful here with the words you have chosen in your question, namely the word “scale”.  There are many types of scales, and our method may vary based on which is to be used.


Method 1
This method assumes a scale which uses balance, something like similar to this:


balance

Image from Presentation Process


Since all the coins are identical aside from weight, if we place equal quantities of coins on either side of this device it will tell us something.   This is true for either of the outcomes: balance or imbalance.


1st Weighing:
We have 12 coins, so naturally we decide to weigh 6 and 6.  In general, there would be the possibility for both balance and imbalance, but since we are told that there does in fact exist a coin which is not the right weight, we cannot have the scale be balanced.  Therefore one side must be heavier.
Since we are not sure if the coin is heavier or lighter it does not matter which collection of 6 I choose to examine further.  Let us pick the heavier side (it makes little difference as we will see).


2nd Weighing:
We have 6 coins, and again I decide to split these and weigh 3 and 3.  If these balance, then it must be that in the other set of 6 is the counterfeit coin which we now know to be lighter than a regular coin (why is this so?).  If these do not balance, then we know the other set of 6 will balance and that a heavier than normal coin is in our current set of 6 (again why?).  [Note that your answer will change based on which 6 you picked in the first weighing]


3rd Weighing:
We take whichever set of 6 is unbalanced and determine which set of 3 is lighter or heavier (depending on our knowledge of the second weighing).  For argument sake, let’s say that our second weighing turned out to be unbalanced.  Therefore, now I wish to examine the heavier set of 3 from our previous weighing (since I know the counterfeit coin is heavier).  I remove any one of the 3 coins and weigh the other two (our method relies on equal quantities of coins, and since 3 is a prime number we cannot split it up “nicely”).  What does it mean if the scale balances?  What if it does not balance?


**Notice that in our example we did not need to use 4 weighings to achieve a result, it can be done in only 3.  However, we require at most 4 to do the job efficiently.  The extra weighing may come into our 2nd Weighing step: if our set of 6 balanced we would have to weigh the other set of 6 (3 and 3) to determine which subset of 3 contains the lighter counterfeit coin.**

Method 2
Suppose now that we did not have a scale that relied on balance but purely on weight, perhaps a bathroom scale or something similar.  Our method will now require some number crunching.


1st Weighing:
Pick any 8 of the 12 coins and record their weight.


2nd Weighing:
Of the 8 coins, pick any 4 and record their weight.


Case 1: 

The average weight of the 4 coins equals the average of the 8 coins. 
This implies that the set of 8 does not contain the counterfeit coin (Why?).  Discard these and examine the 4 unchecked coins.  Note now that we can determine the weight of a true coin (How?).


3rd Weighing (Case 1):
Pick any two of the 4 coins.  If the average of the 2 coins is consistent with the weight of a true coin then we may discard them and consider the other two unchecked coins (similarly if the coins we had picked were inconsistent, then we discard the two unchecked coins).


4th Weighing (Case 1):
Pick either of the two remaining coins and check if it is consistent with a true coin.


Case 2: 

The average weight of the 4 coins is different than that of the 8 coins.
This implies that the set of 8 contains the counterfeit coin (again why?).
Note that we can determine the weight of the 4 coins in our set of 8 which were not in the 2nd weighing.  Let us call the first set of four Group 1, and the second set we will call Group 2.


3rd Weighing (Case 2):
Pick two coins from Group 1 and two coins from Group 2 and record their combined weight.  This weight must be equal to the weight of either Group 1 or Group 2 (Why?).   For argument sake let’s say that it equalled the weight of Group 1.  Then that implies the counterfeit coin was one of the two selected from Group 1; Also that every coin in Group 2 is a true coin, hence we can determine the weight of a true coin.


Now, we are in the same situation as in case one for the 4th weighing and the counterfeit coin can be determined.

Can you think of a better way of solving this problem for different types of scales?  What if you knew the fake coin was heavier or lighter?

Tyler

About Math Central
 

 


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS