In an antique shop the ancient currency expert checking some gold coins from
15th century. He knows that there is one fake coin made up of alloy in a pile
of 70 coins and it is lighter than the original coin.What is the least number of
weight trials on a balance is necessary to find the fake coin?
Here's what I tried:
We can divide the 70 coins into piles of 10 and compare a pair of groups.
The worst case is, the fake coin will be in the seventh pile.
No. of trials required: 3
Then, we will divide the 10 coins into two groups of 5. One will be lighter.
No. of trials required: 1
Then, we can divide the 5 coins into 2 groups of 2, and keep one coin alone. We will compare the groups of 2, one will be lighter (considering the worst case) and we will again compare the individual coins.
No. of trials required: 2
I got the answer: 6. But I am not sure. Can you get a value lower than 6?
Best Answer
The general idea here is to divide roughly the original pile into three roughly equal piles, with at least two of them having the same number of coins. Then, compare the two of them with equal number of coins. This reduces the problem to the pile which is lighter, or to the third pile if those first two piles are equal. One can show that, in $k$ weighings you can identify the offending coin in a pile consisting of up to $3^k$ coins.
In your case ($70$ coins): as $3^3<70\le 3^4$, we should be able to do it with (at most) four steps.
In the first step, divide the coins into three roughly equal piles: $70=24+24+22$ and compare the two piles of $24$ coins. If one of those piles of $24$ is more lightweight than the other, pick it. Otherwise, you pick the third pile. You have spent one weighing and you have reduced the problem to a pile of $24$ or $22$ coins.
Now, if you have $24$ coins, split them into three piles of $8$. If you have $22$, split them as $22=8+7+7$. Compare two piles of equal sizes (in the $2$nd case they will have $7$ coins). Again, you will end up with either a lighter pile of $7$ or $8$ coins, or they will be equal and the lighter coin is in the third pile. So far we've spent two weighings and we have reduced the problem to a pile of $8$ or $7$ coins.
In the next step, divide either $8=3+3+2$ or $7=3+3+1$ and compare two piles of $3$ coins with each other. Either one is lighter or the coin is in the remaining pile. If the remaining pile is the one with only $1$ coin, you have finished with only three weighings. Otherwise, you have spent three weighings and have reduced the problem to $2$ or $3$ coins.
In the last step, you weigh two of those coins against each other. The lighter one is the offending coin, and if you had $3$ coins and you weighed two and they are the same - the offending coin is the third one.