# Solution to the Scales and Counterfeit Coin Problem

The steps necessary to solve the problem depend on the results of each use of the scales. Thus the solution quickly becomes very complicated if mapped out with numbers. Therefore, I present an more abstract solution first and then add the numbers later.

There are four points to solving the problem:

• If we weigh the coins and the left hand side (LHS) turns out to be heavier than the right hand side (RHS) (or vice versa), that knowledge is valuable. We must not lose that information.
• Groups of coins can be combined, so long as they remain distinct groups.
• Until we know whether the counterfeit is light or heavy, when splitting a group of coins into two groups (or three) and comparing (two of) the groups, there are only two possible meaningful outcomes: the scale either balances or it doesn’t. This does not allow us to reduce the number of coins fast enough. With only two possible outcomes, at best only half the coins can be eliminated with each use of the scales. This would suggest that maximum possible is 25= 32. However, once we have compared two groups of coins, then the first point comes into play. We can split the coins into three groups, removing some coins from the scales and swapping other coins from side to side. Now we have three possible outcomes: the balance is restored, the balance stays the same and the balance is reversed. This allows us to reduce the number of coins by two thirds (approx) with each use of the scales.
• Even with the above, it is not possible to solve without one final point. The coins that have been discarded as being true can now be used as standard weights. Of course we must keep track of which these are.

Let us consider families of similar problems.

Consider our problem, but generalized so that our problem with n coins and m weighings is named An,m. Our particular problem is A117,5

For a warm up consider a somewhat different problem, Cn,m. Cn,m is very similar but we know whether the counterfeit is too light or too heavy.. For the purposes of illustration, let us suppose it is too heavy, but the same principle holds if it is too light.

One solution is quite straight-forward. Suppose that n is divisible by three. Then we can divide the coins into three equal groups.

Compare two of the groups. If the scales balance, then the counterfeit is in the third group. Otherwise the heavier group contains the counterfeit.

If C(n) is the number of weighings required to find the counterfeit in n coins, then C(n)= C(n/3) + 1

Since C(1)= 0, C(2)= 1, and even C(3)=1, then the recurrence relation solves to C(n)= log3(n)

If n is not divisible by three, the method can still be applied. No matter what the remainder, always two of the piles will have the same number of coins. However, the worst case is that the larger pile will contain the counterfeit. Therefor for any n, C(n)= ceiling log3(n)

We can solve Cn,m if n <= 3m

We have yet another problem to solve before tackling our original problem.

Consider the problem Bn,m in which:

• we have n coins and m weighings allowed (as before).
• the coins are divided into two equal size groups, one on the left and one on the right. Therefore n is even.
• The pre-knowledge that if the counterfeit is in the LHS, it is heavier than the real coins, and that if it is in the RHS., it is too light. We don’t know which is true, but one them is true.
• we have access to more standard (non-counterfeit) coins than we can need.

One way to reduce the numbers of coins is to move the coins around. However, we must keep track of which coins were moved and which were not:

• remove x=3(m-1) coins from the RHS and put them aside for a moment
• move x coins from the LHS to the RHS
• add x standard coins to the LHS

Note: I am aware of a more elegant symmetrical solution that does not require Cn,m but it only works but only if n is odd !!
Note 2: I no longer can remember this more elegant solution.

When we compare the LHS and the RHS, one of 3 things will happen.

1. The scales will balance, indicating that the counterfeit is among the coins that were removed from the RHS and that the counterfeit is lighter than the other coins. So we know the weight of the counterfeit and we have 3(m-1) coins in that group and m-1 weighings left. This is just Cn,m-1 with n =3m-1 which we know how to solve.
2. The coins on the LHS will be lighter (indicating that the excess weight has shifted): Meaning that the over-heavy counterfeit is among the coins that were moved to the RHS from the LHS and that counterfeit coins is heavier than the others. Again we have no more than 3(m-1) coins, m-1 weighings left and we know the weight of the counterfeit. This is again Cn,m-1 with n =3m-1 which we know how to solve.
3. The group of coins on the RHS is still lighter: So we know that the counterfeit is not among any of the coins that were moved. Therefore we now have the same problem over again with n-2*x coins and m-1 weighings left.

So Bn,m can be solved by reducing the problem to Bn-2*3(m-1),m-1 This recurrence relation is more useful in the form:

If we can solve Bn,m then we can solve Bn+2*3m,m+1

Looking at the lower limit, we inspect the same solution for B2,1 . We have two coins, on on the LHS and one on the RHS: m=1,x=30=1. Thus we move 1 coin off the RHS, 1 coin across and put 1 standard coin in the LHS. In the first two outcomes, we have only one coin in the respective groups and thus it must be the counterfeit. So B2,1 is solvable.

Therefore applying the recurrence relation

B2,1 , B8,2 , B26,3 , B80,4 and   B2*(3(m-1) + 3(m-2) + … + 1),m are all solvable.

Now let’s look at the original problem An,m

On the first weighing we can put (3(s-1) + 3(s-2) + … + 1) coins in each pan, where s= m-1

• If the pans don’t balance, the counterfeit must be among those in the pans, so we are left with problem B2*(3(s-1) + 3(s-2) + … + 1),s which is solvable (see above).
• If the pans do balance the counterfeit must be among those not in the pans, so we are left with problem Am-2*(3(n-2) + 3(n-3)  + … + 1),n-1

So An,m can be solved if An-2*(3(m-2) + 3(m-3) + … + 1),m-1 can be solved. To re-arrange that recurrence relation:

If we can solve An,m then An+1,m+2*3(n-1)+3(n-2)+ . . . +1) can be solved by this method.

Note that A1,1 trivially solved. There is only one coin, so it must be the counterfeit. Iterating backwards then A2,3 can be solved as can A11,3 and A37,4 and A117,5 (which is our given problem).

Now we solve our particular problem, with numbers inserted into the abstract argument above. Our problem is problem A117,5 which is solvable by the outlined general method. (See the previous paragraph.)

We start by placing 40 coins in each tray, leaving 37 coins unweighed.

• If they do not balance the problem is reduced to problem B80,4. Suppose that the LHS is heavier (or walk around the table so that the LHS is the heavier side). Move and set aside 27 coins off the RHS, transfer 27 coins from the LHS to the RHS and add 27 standards to the LHS (from the 40 unweighed, now known to be standard, coins). (Note that a total of 26 coins were not moved.)
• If the LHS is still heavier, then the counterfeit is among the coins that were not moved and we don’t know its weight. This is B26,3. Therefore we repeat the process by removing 9 of the coins from RHS, moving 9 coins from the LHS to the RHS and adding 9 standards to the LHS
• If the scales balance we have an over-heavy counterfeit in the 27 coins removed from the RHS and 4 weighings left. This is just C27,4 and is solved by dividing the 27 coins into 3 equal groups and comparing any two of the groups. This identifies which group it is in leaving C9,3. Successive divisions into 3 equal groups solves this problem.
• If the LHS is now lighter than the RHS then we have an over-light counterfeit in the 27 coins moved form the LHS to the RHS and 4 weighings left. This is just C27,4 and is solved by dividing the 27 coins into 3 equal groups and comparing any two of the groups. This identifies which group it is in leaving C9,3. Successive divisions into 3 equal groups solves this problem.
• If the scales balance, we have the same problem as the original problem but with only 37 coins, but only 4 weighings permitted (ie A37,4) To solve this put 13 coins on each tray and try again, leaving 11 unweighed.
• If they do not balance the problem is reduced to problem B26,3. We start by moving groups of 9 coins around but see above for details.
• We need be concerned only if the scales balance, in which case we have problem A11,3. Put 4 coins on each tray and try again.
• If they do not balance the problem is reduced to problem B2,8 which is solvable.
• We need be concerned only if the scales balance, in which case we have problem A3,2 In this case, put 1 coin on each tray and try again.
• If they do not balance the problem is reduced to problem B2,1 which is solvable by weighing one of the coins against a standard.
• We need be concerned only if the scales balance. But we need not since we are left with A1,1 with only 1 coin. It must be the counterfeit. Note that we have in this particular case only used the scales 4 times.

### Solution for Second Problem:

This is really A118,5

Notice that we based the solution to A117,5 on the fact that A1,1 is solvable. However A2,1 is also solvable, but only if you have a standard coin (which if we get down to A2,1 we have in abundance). A2,1 is easily solved by weighing one of the coins against a standard. If it is not the same then it is the counterfeit. If we propagate back to 5 weighings we find that A118,5 is solvable.

Therefore the solution is exactly the same but with this small change to the end of the problem. We can never get away with only 4 weighings (see the end of the solution for the original problem.).

### Solution for Third Problem:

At first glance one comes to the conclusion that for Bn,m , the maximum value for n must be even; that there must be the same number of coins in each group. However, remember that after the first weighing, we have a whole bunch of standards we can arbitrarily add and remove from groups of coins. For example, we can have two coins in one group and one coin in the other. Weigh the two coins against each other. If they balance, the counterfeit is the single coin. If they do not balance and they came from the heavy side, the heavier coin is the counterfeit. Otherwise it is the lighter coin. Therefor B3,1 is in fact solvable., One can get B3,1 by having two unknown coins in one side and one in the other, along with a standard (you must keep track of which is the standard). By extension B1 + 2*(3(m-1)  + . . . + 1),m= B3m,m is solvable if you have a standard coin.

Therefore when we look at the solution to An,m we can add one more coin to one of the pans than described above and thus change the recurrence relation, so long as we have a standard to counterbalance it. The recurrence relation becomes

If we can solve An,m then An+1+2*3(n-1)+3(n-2),m+1+ . . . +1) can be solved by this method.

Along with the fact that we now know how to solve A2,1 allows us to solve A5,2 and A14,3 and A41,4 and A122,5 . But hold on. When we start the problem we don’t have a standard coin yet! Thus the jump from A41,4 must use the old recurrence relation and we get A121,5. Again to put some numbers on these abstract arguments:

• We start by placing 40 coins in each side, leaving 41 unweighed.
• If they do not balance the problem is reduced to problem B80,4 which is solvable. It starts by moving groups of 27 coins around…
• If the scales balance, we have the same problem as the original problem but with only 41 coins, but only 4 weighings permitted (ie A41,4)
• In the case the scales balanced, put 14 coins on the LHS and 13 coins on the RHS leaving 14 coins unweighed. Now add 1 standard coin on the RHS to equalize the numbers.
• If the scales do not balance the problem is reduced to problem B27,3. This time we will look at what to do if the scales do not balance.
• Remove 9 coins (but not the standard) from the RHS and put them aside. Move 9 coins from the LHS and put them in the RHS. Add 9 standard coins to the LHS
• We have simple solutions if the balance equalizes or shifts to the other side.
• If the balance does not change, then remove all the coins that we shifted around. We are left with 5 coins in the L.H.S. and 4 in the R.H.S. and 1 standard coin in the R.H.S. Repeat moving groups of 3 coins around. Etc.
• If the scales balance we have problem A11,3. Proceed by placing 5 coins on the RHS and 4 on the LHS along with 1 standard. Etc.