Friday, October 10, 2014

Faulty Batch

A little nation in Antarctica has its gold coins manufactured by eight different European companies. The Treasury Minister and his secretary were examining samples just delivered from the eight companies.

"How much should these coins weigh?" the Minister asked.

"Ten grams each, Sir."

"At least one of these coins - this one - is lighter than the others," said the Minister. "Let's check."

He put the coin on the scale, which showed that the coin weighed only nine grams. A bunch of coins, untidily placed on a tray, were frantically searched by the Minister and his secretary. Within the bunch, they found a handful of coins that also weighed one gram less than they should. The two men looked at each other; obviously, one of the manufacturing companies was producing coins with the wrong weight.

"Most of the coins are still packed in the plastic wrappers. It should be easy to tell which company is producing the faulty batch," said the secretary.

The two men placed eight packs of coins on the table, one pack from each company.

"How tedious," sighed the Minister. "Do we really have to use this scale eight more times, just to find the faulty batch of coins?"

"That won't be necessary, Sir," grinned the secretary. "We can find the lighter coins by using the scale only once."

How would they do it?



Notes:
By using the scale once, it means that only one reading can be taken after all the coins to be weighed are placed onto the scale. ie, you cannot read the values as you place the coins on -- that would make the puzzle too easy!

Faulty Batch Puzzle Solution

The secretary placed on the scale 1 coin from the first batch, 2 from the second, and so on until he put 8 from the eighth batch.

If all coins weighed 10 grams each, then the weight displayed on the scale should have been 360 grams ((1 + 2 + ... + 8) × 10). But, since one batch of coins weighs less, the difference between 360 grams and the weight displayed on the scale should point us to the faulty batch. For example, if the faulty batch was the fifth one, then the total weight displayed on the scale would be 355 grams. Or if it was the seventh batch, the weight would have been 353 grams, ie 7 grams less than the theoretical total weight of 360 grams.

An 'optimisation' on this solution is to omit the 8 coins from the eighth batch. In this case, the maximum weight of the coins would be 280 grams, and if it equals 280, then the eighth batch is the faulty one. Thanks to Denis Borris for this observation.

By using the same logic, one could omit the coins from any one of the other batches, instead of the eighth one. For example, if we omit the fourth batch, we'll be left with a theoretical 320 grams and, if it is indeed the total weight, then we will know that the fourth batch was the faulty one. Thanks to Glen Parnell for noticing this.