There are 10 coins of which 5 are fake (counterfeit). The 5 real coins all weigh the same. The
5 fake coins all weigh less than the real coins and all have different weights as well.
Using a balance scale, at worse, how many weighings are required using the best (most efficient) strategy
to identify which coins are real and which are fake?
HINT: With each weighing, either you'll identify, with certainty, 2 real coins (if the
2 coins weigh the same) or 1 fake coin (the coin that weighs the least).
ANSWER:
At worse, 7 weighings are required.
EXPLANATION: Place 1 coin on each side of the balance. If they weigh the same, they are
real and can be set aside (forming a group of real coins). Otherwise, the lighter coin is fake and can be
set aside (forming a group of fake coins). With each weighing, you will identify 1 fake coin or 2 real
coins. Below is an example of the worse case scenario (with the best strategy):
1st Weighing: Scale does not balance, 1 coin (the lighter one) set aside as fake. 9 coins remaining
of which 4 are fake.
2nd Weighing: Scale does not balance, 1 coin (the lighter one) set aside as fake. 8 coins remaining
of which 3 are fake.
3rd Weighing: Scale does not balance, 1 coin (the lighter one) set aside as fake. 7 coins remaining
of which 2 are fake.
4th Weighing: Scale does not balance, 1 coin (the lighter one) set aside as fake. 6 coins remaining
of which 1 is fake.
5th Weighing: Scale balances, both coins set aside as real. 4 coins remaining of which 1 is fake.
6th Weighing: Scale balances, both coins set aside as real. 2 coins remaining of which 1 is fake.
7th Weighing: Scale does not balance, the heavier coins is real, the lighter coin is fake. The 5 fakes
have been identified.
Do you have a
suggestion for this puzzle (e.g. something that should
be mentioned/clarified in the question or solution, bug, typo, etc.)?
