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?
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.