Saturday 30 July 2005

coin weighting problem

coin weighting (ref: http://www.techinterview.org/Puzzles/fog0000000090.html)

you have 12 coins. one of them is counterfeit. all the good coins weight 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 weights. 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 #2..." 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 right tilt, respectively, then coin #11 is heavier than it should be.

this problem is solveable...it 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...


Since the official website does not have a solution (not a sound solution), so I posted my solution online.

1 comment:

Anonymous said...

Si miler question: ref: http://technical-interview.com/puzzles.aspx

You have 12 balls identical in size and appearance but one is an odd weight (it could be either light or heavy).

You have a set of scales which will give three possible readings: Left = Right, Left > Right or Left < Right (I.E Left and
Right have equal weight, Left is Heavier, or Left is Lighter).

You have only three chances to weigh the balls in any combination using the scales. Determine which ball is the odd one and if it's heavier or lighter than the rest. How do you do it?