# Counterfit Coins Puzzle

A king collects 10 gold coins as a tax from each of 10 provinces.

Each coin weighs 10 grams.

The king learned that one province is shaving off 1 gram from each of their coins.

The king examines the coins with a balance scale.

The scale has 2 trays, we label them “A” and “B”.

The scale can provide 3 results, “A<B”, “A>B”, and “A=B”.

**How can the king minimize the number of uses of the scale to find which province is cheating?**

**Solution:**

Take 1 coin from each province and mark / label where it came from.

At each stage, we seek to separate the coins into 3 equal sets.

We only use the scale to compare sets of coins with equal number.

If the scale results is “A=B”, then all of the coins in A and B are true.

Divide the 10 coins into 3 groups, of 3, 3, and 4.

**Weighing 1:** Compare 2 sets of 3.

If one of the sets of 3 is lighter, the problem reduces to that set of 3.

**Weighing 2:** Compare first coin with second coin from the set of 3.

If result is “A=B” then the third is light coin, otherwise the lighter.

If comparing the sets of 3 results in “A=B”, then examine the set of 4.

We divide the set of 4 into sets of 1,1,and 2.

**Weighing 2:** Compare first set of 1 with second set of 1.

If one of the sets of 1 is light we have the answer, otherwise

**Weighing 3:** Compare final 2 coins.

There is 80% probability that we will only use the scale twice.

**Expected number of uses of scale = 2.2.**