Fog Creek Software
Discussion Board

even harder coin problem

Solution to:

even harder coin problem  aha:!


some of you may have easily solved the pill weighing problem posed here. if so you are going to love this problem.
it is similar but much more difficult.
from my buddy tom:
> ok, here's a tough one (i thought).  there are no "aha!" tricks - it
> requires straightforward deductive-reasoning.
> you have 12 coins.  one of them is counterfeit.  all the good coins weigh
> the same, while the counterfeit one weights either more or less than a
> good coin.
> your task is to find the counterfeit coin using a balance-scale in 3
> weighs.  moreover, you want to say whether the coin weighs more or less
> than is should and, and this is the real kicker, your weighs must be
> non-adaptive.
> that is, your choice of what to put on the balance for your
> second weigh cannot depend on the outcome of the first weigh and your
> decision about what to weigh for round 3 cannot depend on what happened on
> either your first or second weigh.
> for example, you can't say something like "take coin #1 and coin #2 and
> weigh them.  if they balance, then take coins 3,4,5 and weight them
> against 6,7,8...if 1 and 2 don't balance, then weigh #1 vs #12..."  you
> have to say something like:
> round #1: do this
> round #2: do this
> round #3: do this
> if the results are left tilt, balanced, and left tilt, respectively, then
> coin #11 is heavier than it should be.
> this problem is took me about 1-2 hours of working on it to
> get it.  i think even finding the counterfeit using an adaptive solution
> is tough.  then non-adaptive constraint  makes it quite hard and having to
> find whether it's heavier and lighter is cruel and unusual riddling ;-)
> have fun...


OK… I’ll posit the following solution for the hard coin problem:

Weighing left versus right:
Step 1.  Weigh 1-2-3-4-5-6 versus 7-8-9-10-11-12
Step 2:  Weigh 1-3-5-7-9-11 versus 2-4-6-8-10-12
Step 3:  Weigh 1-4-7-10 versus 2-5-8-11

Solution Table for Right Beam Up (reverse senses for right down <or lighter>):

(u == right up)  (d == right down)  (e == even)

Heavier Coin    Step 1    Step 2    Step 3
1        u    u    u
2        u    d    d
3        u    u    e
4        u    d    u
5        u    u    d
6        u    d    e
7        d    u    u
8        d    d    d
9        d    u    e
10        d    d    u
11        d    u    d
12        d    d    e

Mike Donovan
Lakewood, Colorado

James M 'Mike' Donovan
Tuesday, December 25, 2001

Your solution seems to assume that the bad coin is always heavier.  It isn't.  It might be lighter.

You're kinda on the right track though, even so.

Paul Brinkley
Thursday, December 27, 2001

As I stated in my solution:

"Solution Table for Right Beam Up (reverse senses for right down <or lighter>):"

Reverse the up-down senses for lighter coins.

Mike Donovan

James M 'Mike' Donovan
Thursday, December 27, 2001

Mike: your solution has a problem ... your mapping isn't unique when you consider both the heavy and lighter coin cases.  For example, "ddu" maps to 7-heavy, but also maps to 2-light as well.

I don't have a solution but I admire the problem ... *grin*

Thursday, December 27, 2001

Sorry – next attempt:

<one solution of many>

1:  Weigh      v
2:  Weigh  v
3:  Weigh      v

u = right up
d = right down
e = balance even

Coin  Heavier  Lighter
1        d.d.e      u.u.e
2        d.d.u      u.u.d
3        d.e.d      u.e.u
4        d.e.e      u.e.e
5        u.e.d      d.e.u
6        u.d.u      d.u.d
7        u.d.e      d.u.e
8        u.u.u      d.d.d
9        e.u.u      e.d.d   
10      e.u.e      e.d.e
11      e.u.d      e.d.u
12      e.e.d      e.e.u

Octal ‘rithmatic makes my head hurt.

Mike Donovan

James M 'Mike' Donovan
Friday, December 28, 2001

I didn't check every case you just put down, but it looks like you've got it now.

Another reason I knew for sure that your first solution wouldn't work, was because you were weighing all 12 coins in the first two weighings. 

A balance scale is a ternary device; each weighing can result in left-heavy, right-heavy, or balance.  Therefore the best you can do in a weighing is to winnow the possible cases down to a third of what they were before.

You start with 24 possibilities (heavy or light for each of the 12 coins - 12 times 2).  The first weighing should narrow it down to 8; the second down to 3 or 2; the last brings you to 1.  Weighing four coins on each side at first does the right thing.  If you work it out, you'll find that each result indicates 8 possible cases left.

Weighing six coins on each side, however, means you can't possibly get the balance result, and the other two result in 12 cases left.  There's no way to narrow that down in just two weighings unless you get lucky.

Paul Brinkley
Wednesday, January 2, 2002

Paul - you were absolutely correct, of course.  My ten-minute solution didn't work but the half-hour version was better.

I reasoned that the problem dealt with three possible states for 24 combinations, so it could be modelled with octal numbers (here, in base 3) from 000 through 222.  There are 27 numbers to choose from, so we have three left over.

The fun part was to find pairs which totalled 222 and apply that to the specified machine states, while constraining the combinations to have four each of zeroes, ones, and twos in each of our three columns (one for each weighing):

221 001

220 002

212 010

211 011

012 210


James M 'Mike' Donovan
Wednesday, January 2, 2002

Yep.  And credit where credit is due: I never thought of thinking about the problem like you did (not to mention a few others).  I used the same reasoning technique I used to do the original problem, which resulted in a longer trip to the answer.  But I got there.  It might be in the archives, which don't seem to be online anymore.

Paul Brinkley
Thursday, January 3, 2002

*  Recent Topics

*  Fog Creek Home