Note: your browser needs to be able to handle superscripts
and subscripts in order to make sense of this page. If An,m
appears without subscripts and 3n without superscripts, then
you have a problem.
Solution:
The tree of steps to take depending on the results of each use of the scales
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 three keys to solving the problem:
- If we weigh the coins and the LHS turns out to be heavier than the 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.
- 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 key 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.
We have:
- n coins including one counterfeit
- The counterfeit is known to be to heavy (or known to be to light,
take your pick)
- m allowed weighings
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 while if either of the sides of the scale is heavier,
then that 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 different problem to solve before tackling
our real problem. This is, however, the key to solving our problem.
Consider another problem
Bn,m .
In this problem we have:
- n coins and m weighings allowed.
- that the coins are divided into two equal size groups, one on the left and
one on the right. Therefore n is even.
- The knowledge that if the counterfeit is in the L.H.S. (left hand side), it is
heavier than the real coins,
and that if it is in the R.H.S., it is too light.
- more standard coins than we can need.
One way to reduce the numbers of coins is to:
- remove x=3(m-1) coins from the R.H.S. and put them aside
for a moment
- move x coins from the L.H.S. to the R.H.S. but keep them separate from
those that have not been moved from the R.H.S.
- add x standard coins to the L.H.S. but keep them separate from those
already there.
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 !!
When we compare the L.H.S. and the R.H.S., one of 3 things will happen.
- The scales will balance, indicating that the counterfeit is among
the coins that were removed from the R.H.S. and that the counterfeit is
lighter than the other coins. So we know the weight of the counterfeit
and we have no more than 3(m-1) coins, m-1 weighings left.
This is just Cn,m-1 with n <=3m-1 which we
know how to solve.
- be lighter on the L.H.S. (the excess weight has shifted):
Meaning that the over-heavy counterfeit is among the coins that were moved to
the R.H.S. from the L.H.S. 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.
- be still heavier on the R.H.S.: 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 B
n,m can be solved by reducing the problem to
B
n-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 Bn,1
. We only have 1 weighing left (m=1,x=1=30). Thus we move 1
coin off the R.H.S., 1 coin across and put 1 standard coin in the L.H.S.
In the first two outcomes, we have only one coin in the respective groups
and thus it must be the counterfeit. However, in the outcome that the balance
does not change, we don't have any more weighings. Therefore there had
better not be any coins not moved, so m/2=1. 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 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 A
n,m can be solved if A
n-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
which is solvable. Suppose that the R.H.S. is heavier.
Move and set aside 27 coins off the R.H.S., transfer 27 coins from the
L.H.S. to the R.H.S. and add 27 standards to the R.H.S. (from the 40 unweighed,
now known to be standard, coins). (Note that a total of 26 coins were not moved.)
- If the R.H.S. 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 R.H.S., moving
9 coins from the L.H.S. to the R.H.S. and adding 9 standards to the L.H.S.
- If the scales balance we have an over-heavy counterfeit in the 27 coins
removed from the R.H.S. 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 R.H.S. is now lighter than the L.H.S. then we have an over-light
counterfeit in the 27 coins moved form the L.H.S. to the R.H.S. 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
which is solvable. We start by moving groups of 9 coins around but see
above for details.
- So 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.
- So 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.
- So 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 L.H.S. and 13
coins on the R.H.S. leaving 14 coins unweighed. Now add 1 standard coin
on the R.H.S. 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 R.H.S. and put them
aside. Move 9 coins from the L.H.S. and put them in the R.H.S. Add 9 standard
coins to the L.H.S.
- 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 R.H.S. and 4 on the L.H.S. along with 1 standard.
Etc.
