Counterfeit Coin Challenge

Date: 05/12/2007 at 09:36:36
From: John
Subject: Coin Challenge with 2 Light Counterfeits

You are presented with a set of 13 suspect coins.  Of these, it is
known that the number of counterfeit coins is either 0 or 2.  All of
the counterfeit coins, if any, are known to have come from a single
batch of light coins.  You must identify the counterfeit coins, if
any, after 4 weighings or fewer.

Date: 05/12/2007 at 13:23:59
From: Doctor Vogler
Subject: Re: Coin Challenge with 2 Light Counterfeits

Hi John,

Thanks for writing to Dr. Math.  The trick with these 
coins-on-a-balance problems is that the balance only distinguishes
three different cases:

  (1) both sides weigh the same
  (2) the left side is heavier than the right
  (3) the right side is heavier than the left

That means that one weighing on the balance can only tell apart three
different scenarios.  Two weighings can only tell apart 3^2 = 9
different scenarios.  With n weighings, you can tell apart 3^n
different scenarios.  In your case, there are 13-choose-2 or 78
different ways that the 2 light coins could be hidden among the 13
coins, and one way that they are all identical, giving a total of 79
scenarios.  That's pretty close to the optimum 81 scenarios you can
distinguish with 4 weighings, so you don't have a lot of wiggle room.

Your job is to figure out how to arrange coins on the two balance
trays in order to divide those 79 scenarios as evenly as possible into
three cases:

  (1) at most 27 scenarios where both sides weigh the same
  (2) at most 27 scenarios where the left is heavier
  (3) at most 27 scenarios where the right is heavier

Then for each of those results, you need to decide how to arrange
coins on the two balance trays in order to divide the at-most-27
scenarios into three more cases:

  (1) at most 9 scenarios where both sides weigh the same
  (2) at most 9 scenarios where the left is heavier
  (3) at most 9 scenarios where the right is heavier

and so on.

Does that make sense?  If you have any questions about this or need
more help, please write back and show me what you have been able to
do, and I will try to offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/12/2007 at 14:52:36
From: John
Subject: Coin Challenge with 2 Light Counterfeits

You weigh: 1 2 3 4 5 6 against 7 8 9 10 11 12
Result #1:  The balance remains in the middle.

So Coin 13 is not a light coin

You weigh: 1 2 3 against 4 5 6
Result #2:  The balance tips to the left.

1 2 3 are normal and either 4 5 or 6 is light

You weigh: 7 8 9 against 10 11 12
Result #3:  The balance tips to the left.

7 8 9 are normal, second light coin is 10 11 or 12

...too many options left open, first weigh needs to narrow more down.

Date: 05/12/2007 at 18:01:18
From: Doctor Vogler
Subject: Re: Coin Challenge with 2 Light Counterfeits

Hi John,

Let's see if I can help you with that first weighing.  You probably
already noticed that you have to put some number (say n) of coins in
the left side (and we might as well label these coins 1, 2, ... n),
and the same number of coins in the right side (n+1, n+2, ... 2n).

If the balance is level, that means that either

  (a) there is no light coin at all,
  (b) both light coins are in the 13-2n that we didn't weigh, or
  (c) one light coin is in each side of the balance.

Of our original 79 scenarios, there is 1 for (a), (13-2n)*(13-2n-1)/2
for (b), and n^2 for (c), so the balance is level in

  1 + (13-2n)(13-2n-1)/2 + n^2

scenarios.

If the balance tips to the right, so the right side is heavier, then
that means that either

  (a) there is one light coin in the left side and one unweighed, or
  (b) both light coins are in the left side.

Of the original 79 scenarios, there are n(13-2n) for (a) and n(n-1)/2
for (b), so the balance tips to the right in

  n(13-2n) + n(n-1)/2

scenarios.

Similarly, the balance tips to the left in

  n(13-2n) + n(n-1)/2

scenarios.

You want to choose n so that all three of those numbers are less than
or equal to 27.

By the way, you should double-check your arithmetic to make sure that

  [1 + (13-2n)(13-2n-1)/2 + n^2] + 2*[n(13-2n) + n(n-1)/2]

is exactly 79 no matter what n is.  If not, then you didn't count
where all of the scenarios go.  Remember that every possibility will
either leave the balance level or tip it one way.

So how many do you think you should weigh first?  And why?

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/