
even harder coin problem
Solution to:
even harder coin problem aha:!
PROBLEM:
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 deductivereasoning.
>
> 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 balancescale 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
> nonadaptive.
>
> 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 solveable...it took me about 12 hours of working on it to
> get it. i think even finding the counterfeit using an adaptive solution
> is tough. then nonadaptive constraint makes it quite hard and having to
> find whether it's heavier and lighter is cruel and unusual riddling ;)
>
> have fun...
SOLUTION:
OK… I’ll posit the following solution for the hard coin problem:
Weighing left versus right:
Step 1. Weigh 123456 versus 789101112
Step 2: Weigh 1357911 versus 24681012
Step 3: Weigh 14710 versus 25811
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 updown 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 7heavy, but also maps to 2light as well.
I don't have a solution but I admire the problem ... *grin*
Alyosha`
Thursday, December 27, 2001
Sorry – next attempt:
<one solution of many>
1: Weigh 5.6.7.8 v 1.2.3.4
2: Weigh 8.9.10.11 v 1.2.6.7
3: Weigh 2.6.8.9 v 3.5.11.12
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 leftheavy, rightheavy, 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 02, 2002
Paul  you were absolutely correct, of course. My tenminute solution didn't work but the halfhour 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
etc.
James M 'Mike' Donovan
Wednesday, January 02, 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 03, 2002
Recent Topics
Fog Creek Home
