You have 25 gold coins. One on these coins is a counterfeit
and weighs lighter, while
the rest of the coins have the same weight. If you have a balance, how
would you determine which coin is the lighter one with 3 weighings.
Solution:
Divide the coins into 3 group consisting of 9 coins, 9 coins,
and 7 coins. On the first weighing, weigh the 2 groups of nine
coins. If they have the same weight, then the counterfeit is in the group
with 7 coins. If one of the group of 9's weighs less, then the counterfeit
is on that group.
On the second weighing, divide
the group where you know the counterfeit coin is into 3 subgroups, where the
first two subgroups would have 3 coins each. Weigh these first two
subgroups. If they have the same weight then the counterfeit is on the
third subgroup. If one of them weighs less, the counterfeit is on the
subgroup that weighs less.
Since the subgroup that contains the counterfeit has at most
3 coins. Weighing two of these coins will allow you to know which coin
is the counterfeit.
