14. There are seven stacks of coins that look the same. Each stack has exactly 100 coins.
There are two stacks that have counterfeit coins, and all 100 coins in each of those two
stacks are counterfeit. Your task is to figure out which two of the seven stacks contain
the counterfeit coins.
The counterfeit coins weigh 11g each, while the real coins weigh 10g each. You have
an electric balance, but you can only use it to make one measurement.
How can you determine which two stacks contain the counterfeit coins with only one
use of the balance? Explain why the strategy works.
(Hint: Think about taking different numbers of coins from each of the stacks and placing
them on the balance together. Think about the important numbers in the binary number
system.)
We would like to take a different number of coins from each stack so that we know
which stacks have the counterfeit coins. If the question had just 1 counterfeit coin pile,
then we could just take 1 from the first, 2 from the second, 3 from the third and so on.
Note: if there were no counferfeit coins, the total weight taking one from the first pile
(7)(7+1)
and 2 from the second and so on would be
= 28.
2
However we cannot do that this time, because we wouldn’t be able to know for sure
which piles had the counterfeit coins.
For example if the total weight was 33, then there could be 2 possibilities including
the 1 and 4 or 2
and 3 . But we want to avoid these ambiguous situations.
To do this, we basically want to write a 7-digit binary number with two 1’s.
0
From the 1 stack, we take 2
= 1.
1
From the 2
stack, we take 2
= 2.
2
6
From the 3
stack, we take 2
= 4 and so on until you take 2
= 64.
Then when you weigh them, and convert this number in decimal form to binary form,
and from the position of the two 1’s you can easily determine which piles contains the
counterfeit coins.
13