Fog Creek Software
Discussion Board




even harder coin problem solution

The key is, the 3 weighs can give you 27 possible outcomes (BBB, BBL, BBR, BLB,BLL,BLR.... etc, where BLR means Balance on first weigh, Left-tilt on second, Right-tilt on 3rd).  We only need 12*2 = 24 outcomes to uniquely idenity one of the culprits (coin 6 heavier, coin 3 lighter, ...etc.).
Having got that, the job is simply to set what to weigh in each of the 3 attempts, to get a unique result for each culprit.  I thought it would take me several trial and error attempts, but to my own surprise I hit it almost instantly.
So you might try that now, but If you don't feel that lucky, here is one of the many ways you can weigh: 

  i. Left {1,2,3,4,5}, Right{7,8,9,10,11}      (6,12 aside)
ii. Left {2,3,6,8,9}, Right {10,11,12,4,5}  (1,7 aside)
iii. Left  {2,9,11,12,5}, Right {1,4,6,7,8}    (3,10 aside)

I leave it to you to figure out which result maps to which culprit.  Unless I had a typo above, that should work.

yvcb
Friday, December 20, 2002

Well I could give an example, lets consider 5 is heavier, then first weigh gives Left-tilt, 2nd weigh a Right-tilt, and 3rd one Left again.  So the outcome is LRL. You can trace it backwards too.

yvcb
Friday, December 20, 2002

Oops, back-tracing uncovers that LRL is possible when 8 is lighter or 5 is heavier.  So I wasn't all that lucky. But, u can play around to fix it.

yvcb
Friday, December 20, 2002

Your method can't tell the difference between 6 and 12

Paul Viney
Thursday, January 02, 2003

*  Recent Topics

*  Fog Creek Home