# Balance and coins

"A long time ago, merchants from all corners of the world used balances to distinguish counterfeit gold coins..."

Whether history or fiction, the story of the merchant and the fake coin has inspired a large number of interesting puzzles. The main idea is always the same: a merchant has some gold coins some fair and some counterfeit. The fake coins have been made by a skillful thief and look identical to the real coins, except for their weight. The merchant has a balance that allows him to compare the weight of two groups of coins. Can he distinguish the fake coins from the fair coins?

There are probably hundreds of variations on the puzzle, specifying different number of coins and different constraints on the weightings. But such puzzles are more than simple brain-teasers, they have interesting interpretations on Complexity, Information and Communication theory. I will try to shine some light on those ideas in future posts.

Below are some some examples of Balance and Coin puzzles. They are ordered by difficulty and try to showcase some of the different ideas that one encounters in such brain-teasers. In each one of the problems the balance has two arms and a weighting consists of placing some coins on each arm and observing which arm is heavier (or whether they are equal).

The nine coin puzzle:
This is probably the the simplest (and still challenging) of all balance and coin puzzles. Make sure you know how to solve it before moving to harder ones:

• You have 9 coins.
• One coin is fake.
• The fake coin weighs less than the others.
• Find the counterfeit with 2 weightings.

The five coins, one good one bad:
I found this puzzle in Cut-The-Knot and it's a very good introduction to Balance and Coin problems.

• You have 5 coins.
• One coin is fake.
• The fake coin weighs more or less than the others.
• One of the good coins is marked with an X.
• Find the counterfeit with 2 weightings.

The three pairs of coins:
This version of the balance and coins puzzle is simple and clever. I’m unsure of its origin but I have seen it around the web several times.

• Three shoppers give you each a pair of coins.
• In each pair there is one regular coin and the a fake one.
• all fake coins weigh the same, and weigh less than the regular coins.
• Determine which are the three fake coins with 2 weightings.

Note: This is not the same as finding three fake coins among a group of six, because you can distinguish among the pairs. In other words, you can assume each shopper signs the coins with it’s initials.

The 12 coin problem:
This might be the most famous example of a Balance and Coin problem. I understand it is a very old problem, but I found it from “More Games for the Super Intelligent” by James F. Fixx.

• You have 12 coins
• One coin is fake
• The fake coin weighs more or less than the others.
• Find the counterfeit with 3 weightings and determine if it weighs more or less.

Variations

1. With 13 coins find the fake one.
2. With 14 coins, where one regular coin is marked, find the counterfeit and determine if it weighs more or less.
3. With 15 coins, where one regular coin is marked, find the counterfeit.

The N coin problems:
I hear this fantastic puzzle from Eric Naslund, who in turn first heard it from John Conway. I find the puzzle to be very challenging and the solution very gratifying.

• You have N regular coins and 4 counterfeits that all look alike (N + 4 total coins).
• N is not 4.
• The fake coins weigh the same and less than the other coins.
• Find one regular coin with 2 weightings.

This puzzle is slightly different than the others and, in my opinion much harder. To begin with, it doesn't ask for the fake coins, but for a fair one. Notice that if we chooses a coin at random, there is high probability (i.e. N/(N+4)) of choosing a fair coin. The challenge is to chose the fair coin with probability 1, using the balance twice.

HINT: Try separately the cases for N large and N small.

Bonus: Can the problem be solved for N=4?