Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Minimal Weighings of Ten Coins to Identify the Two Counterfeits

Date: 04/18/2010 at 03:19:13
From: ching
Subject: weighings

Suppose you have a balance scale and 10 similar coins, but 2 of them are
fake. The counterfeits have the same weight, but are lighter than the real
ones.

At least how many weighings on the scale do you need to find the fake
coins?

I think you need at least three weighings to identify the fake coins.

Since the question asks "at least how many ...," you have to consider the
best case scenario. First, split the coins into two piles. If you are
lucky, you can determine immediately which group of 5 contains the fake
coins because it is lighter than the other.

Next, get one coin from the pile with all the real coins, setting aside
the rest of that pile. Take that coin you know to be real and add it to
the pile of five that contains the two fake coins. If you are lucky again,
when you split those six coins into two piles and put them on the scale,
you can find in the first try which pile of three contains the two fake
coins.

Set aside all the real coins, add one real coin to the group that contains
the fake coins, then separate them into piles of two. If you are lucky for
the third time, you will find out which group of two coins is lighter --
and those are the two fake coins.



Date: 04/18/2010 at 05:52:23
From: Doctor Jacques
Subject: Re: weighings

Hi Ching,

I think you misunderstood the meaning of "the least number of weighings."
If you only consider the best case, there is a solution (involving a lot
of luck) in two weighings:

* Place one coin on each pan. If you are lucky, one of the coins is
  counterfeit.

* Place two other coins on the balance. If you are still lucky, one
  of these is also counterfeit.

The way I understand the question, you must attempt to find a procedure
that works in _all_ cases, i.e., to find a procedure in N weighings that
will always allow you to identify the fakes.

You are only required to find a lower bound w on the number of steps. In
other words, you want to prove that no procedure in fewer than w weighings
will give you the solution in all cases. Of course, if you find a
procedure in N (>= w) weighings, that would be better still; and the best
would be to find a procedure in exactly w weighings, if such a procedure
exists. But this may be to hard to find.

In this kind of problem, you must compare the number of possible answers
to the number of possible experimental outcomes. If the problem can have x
different answers, and the procedure can give y different results, you
must have y >= x to allow you to discriminate the results.

In this case, the number of answers is the number of subsets of two
elements in a set of 10, namely C(10,2) = 45. This means that your
procedure must give at least 45 possible results.

A single weighing can give 3 results: left pan heavier, right pan heavier,
or equilibrium. In a procedure with w weighings, the number of results is
3^w: each additional weighing multiplies the number of results by 3.

To give at least 45 answers, you must have 3^w >= 45, which means that you
must have w >= 4, since 3^4 = 81 > 45 and 3^3 = 27 < 45.

This proves that no procedure in fewer than 4 weighings will work in all
cases; but it does not prove that there exists an effective procedure in 4
weighings (I don't know if such a procedure exists).

Note that there is a solution in a finite number of weighings: you can
simply weigh together all the 45 possible pairs of coins.

If you want to try to find an effective procedure (not that you are
required to do that, but it may be fun), you should try to ensure that,
after each weighing, the number of remaining possible answers is at most
3^k, where k is the number of remaining weighings. This must be true for
each of the possible outcomes of the previous weighing. Usually, you
should try to ensure that each weighing splits the number of remaining
possibilities in 3 almost equal parts.

Let me illustrate this with an example. Let us try to see if we can start
by weighing 3 coins against 3, i.e., we place coins {1,2,3} on the left
and coins {4,5,6} on the right.

If we have equilibrium, there are two possible cases:

case 1: the two bad coins are in the remaining 4 coins not on the scale.
        This gives C(4,2) = 6 possibilities.

case 2: one bad coin is in each pan. There are 3 possibilities for
        each pan, for a total of 9.

To summarize, if we have equilibrium, there are 6 + 9 = 15 remaining
answers.

If the left pan is heavier, we have also two possible cases:

case 1: the two bad coins are in the right pan. This gives
        C(3,2) = 3 possibilities.

case 2: one bad coin is in the right pan, and the other one is mixed in
        with the remaining coins. There are 3 possibilities for the
        first coin, and 4 for the second coin, for a total of 12.

In this case, we again have 3 + 12 = 15 possibilities.

If the left pan is lighter, the result is the same, by symmetry: we also
have 15 possibilities.

We see that, whatever the outcome of the first weighing, we are left with
15 possibilities, for a total of 45, as it should be. This means that it
may be possible to continue the procedure in 3 weighings, since 3^3 > 15.
In addition, as we have split the possibilities equally, we may hope that
this is the best we can do (although this is not a proof).

The next step would be to devise the second weighing in such a way that,
for each possible outcome, the number of remaining possibilities is at
most 3^2 = 9. Note that the second weighing may depend on the outcome of
the first.

We may also ask if our choice of 3 + 3 for the first weighing is the only
possible choice. If we try to weigh one coin against another, in case of
equilibrium, we have the following remaining possibilities:

case 1: one bad coin in each pan; this is one possibility.

case 2: two bad coins in the remaining eight. This is
        C(8,2) = 28 possibilities.

This gives a total of 29 possible answers in case of equilibrium. As 
29 > 3^3, we cannot hope to finish the procedure in 3 steps. On the other
hand, if I am not mistaken, each of the other choices 
(2 + 2, 4 + 4, 5 + 5) leaves a number of possible answers less than 27.
However, the choice 3 + 3 splits the answers equally in three groups of
15, which means that the worst case is at most 15, and this is less than
for the other choices. This suggests trying 3 + 3 as the first weighing.

Since you are not required to do so, I don't know if you want to try to
find an effective procedure. But if you do, beware that this may involve a
lot of work -- and I'm not sure that such a procedure (in 4 weighings)
exists.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Logic
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/