Puzzle Time - The Commemorative Coin
-
PUZZLE: The Commemorative Coin
You have 16 coins of which eight weigh 10 grams each, and the remaining eight coins weigh 11 grams each. One of the coins is an easily identifiable commemorative coin, and you need to know whether it is a light coin or a heavy one. Can you figure this out using just three weighings, using just the given coins, on a balance scale?
-
PUZZLE: The Commemorative Coin
You have 16 coins of which eight weigh 10 grams each, and the remaining eight coins weigh 11 grams each. One of the coins is an easily identifiable commemorative coin, and you need to know whether it is a light coin or a heavy one. Can you figure this out using just three weighings, using just the given coins, on a balance scale?
@jon-nyc I assume you do not have "standard" weights to compare against, right?
In other word, you just way the coins against each other, not against a standard
-
@jon-nyc I assume you do not have "standard" weights to compare against, right?
In other word, you just way the coins against each other, not against a standard
@taiwan_girl Yep.
-
Yes.
:::
Non-constructive information theory proof: Each weighing gives you 1.5 bits of information (three possible outcomes). Hence three weighings = 4.5 bits. With 4 bits one can count to 16, hence that's more than enough to identify one of the sixteen.
:::
-
Yes it can be done but only in an adaptive solution. That’s what makes it interesting.
Here’s the solution given:
SOLUTION: Note first that it never pays to compare different numbers of coins on the two pans, since the larger group will always outweigh the smaller.
Weighings that balance are dangerous, in a sense, because if all three of your weighings balance, there's no way you can determine the weight of any coin. (Reason: changing the weight of every coin wouldn't change the outcome.) So you probably want the first weighing to involve a lot of coins, so that it tends not to balance (thus if it does, you get some useful information.)
A little reflection will show you that weighing 7 against 7 gives you strictly more information than weighing 8 against 8, if the weighings balance. This is because if seven balance against seven, the two omitted coins must be the same weight; thus, if you added one to each pan, the scale would still balance. So let's try weighing X, A, B, C, D, E, and F against G, H, I, J, K, L, and M.
If the scale tips left, we know at most three of X, A, B, C, D, and F are light. Weigh X against A, say; of course if the scale tips, you're done. Otherwise weigh both X and A against B and C. Again if the scale tips, you're done, but if it fails to tip, you're done too! Why? Because then X, A, B, and C are all the same weight and they can't all be light.
A similar strategy works when the scale tips right. What if it balances?
Then the omitted coins, N and O, must weigh the same; weigh them against X and A. If the scale tips, weighing X against A will seal the deal. Otherwise, X, A, N, and O are all the same weight and we can compare them with B, C, D, and E. This must tip because if X, A, B, C, D, and E were all the same weight, the first weighing would not have balanced. And now you're completely done.
There are other solutions, but as far as I know, none that aren't adaptive; in other words, you seem to need to see the results of earlier weighings before deciding what to weigh next.
There's a lot to be said, though, for the simple, non-adaptive, randomized scheme described in the hint. It succeeds better than 99.99% of the time!
-
Yes it can be done but only in an adaptive solution. That’s what makes it interesting.
Here’s the solution given:
SOLUTION: Note first that it never pays to compare different numbers of coins on the two pans, since the larger group will always outweigh the smaller.
Weighings that balance are dangerous, in a sense, because if all three of your weighings balance, there's no way you can determine the weight of any coin. (Reason: changing the weight of every coin wouldn't change the outcome.) So you probably want the first weighing to involve a lot of coins, so that it tends not to balance (thus if it does, you get some useful information.)
A little reflection will show you that weighing 7 against 7 gives you strictly more information than weighing 8 against 8, if the weighings balance. This is because if seven balance against seven, the two omitted coins must be the same weight; thus, if you added one to each pan, the scale would still balance. So let's try weighing X, A, B, C, D, E, and F against G, H, I, J, K, L, and M.
If the scale tips left, we know at most three of X, A, B, C, D, and F are light. Weigh X against A, say; of course if the scale tips, you're done. Otherwise weigh both X and A against B and C. Again if the scale tips, you're done, but if it fails to tip, you're done too! Why? Because then X, A, B, and C are all the same weight and they can't all be light.
A similar strategy works when the scale tips right. What if it balances?
Then the omitted coins, N and O, must weigh the same; weigh them against X and A. If the scale tips, weighing X against A will seal the deal. Otherwise, X, A, N, and O are all the same weight and we can compare them with B, C, D, and E. This must tip because if X, A, B, C, D, and E were all the same weight, the first weighing would not have balanced. And now you're completely done.
There are other solutions, but as far as I know, none that aren't adaptive; in other words, you seem to need to see the results of earlier weighings before deciding what to weigh next.
There's a lot to be said, though, for the simple, non-adaptive, randomized scheme described in the hint. It succeeds better than 99.99% of the time!
-
