IBM Ponder This #050 · June 2002

This month's puzzle is based on a suggestion of Alex Marmer. It's another coin-weighing problem.

You are given a scale with two pans. This scale will report the difference, in grams, between the masses on the two sides, as well as telling you which side is heavier. So if you place 25 grams on the left pan and 27 grams on the right, you find out that the right side is heavier by 2 grams.

You are given N bags of coins, apparently identical. Each bag contains ten coins. Exactly one bag is full of counterfeit coins, and the rest are full of honest coins . All honest coins are equally massive, all counterfeit coins are equally massive, and counterfeit coins are heavier than honest coins. But you don't know beforehand the masses of honest coins or of counterfeit coins.

You are given the opportunity to make three weighings on your scale, after which you must decide which bag is bogus. You're allowed to open the bags and use an arbitrary number of coins from each bag, if that helps; just keep track of where you got the coins.

What is the largest value of N which can be accommodated?

Solution

Best opened after a real attempt

To be added.