Anyway, its a pretty neat solution:
1. Weigh 13 coins against 13 coins.
If they come out equal, then you have 3 weightings left, 14 unknown coins and a reserve of 26 coins you know are not counterfeit. That will be easy to solve:
2a. Weigh 9 unknown coins against 9 in the reserve.
If the 9 come out heavy (light), then you have two measuerments left and you know the coin is in those 9 and heavy (light), so we have already solved this problem. If the 9 come out even then we have a reserve of 35 coins and 5 unknown with 2 measurements left.
3a. Weigh 3 unknown against 3 from the reserve.
Again, if the 3 are heavy (light), then you have one measuerment left and you know the coin is in those 3 and heavy (light), again we have already solved this problem. Finally if they are equal then we have 1 measurement left and a reserve of 38 coins with 2 unknown coins. At this point the solution is trivial.
From the solution we have so far, it is easy to see the power of a large reserve of coins that are promised not to be counterfeit. Given an infinite reserve and N measurements, it is easy to construct a solution that works for (3N+1)/2 unknown coins (the sum of the first N-1 powers of 3, plus 1). By contrast, when you are told that the coin is heavy, you get 3N, so not knowing the relative weight of the coin approximately doubles how many coins you can solve for. This kind of makes sense, as you sort of eliminate half the hypothetical possibilites for the counterfeit coin.
Anyway, back to step one, suppose one side came out heavier, now you have a reserve of 14 coins and 13 "possibly heavy" coins and 13 "possibly light" coins:
2b. Weigh 9 of the possibly light coins with 4 of the possibly heavy coins against 4 of the possibly light coins with 9 of the reserve coins.
You have left behind 9 of the possibly heavy coins and have 2 measurements left. If measurement 2b comes out equal, then you know it is in those 9 and heavy, easy to solve. If the side with the 9 light coins comes out light, then only those 9 can be to blame (there were no possibly heavy coins on the other side) and so you know it is in those 9 and light.
In the last case to solve the side with the 9 light coins came out heavy, in that case it could have either been due to the 4 possibly heavy coins of the 4 possibly light coins. We have 2 measurements left and a reserve of 32 coins. Now our reserve is large enough that we can do a more brute force soltuion:
3b. Weigh 3 of the possibly heavy coins with 3 of the possibly light coins against 6 reserve coins.
If the coins come out heavy, we know it is in the 3 and heavy. If they come out light, we know it is in the 3 and light. We have one measurement left, so both these cases are easy. Finally if they come out even we only have 2 unknown coins left and a large reserve. We don't even need to make use of the fact that we know the coin is "either heavy and this one or light and that one".
Technically, this completes the solution. However, out of a matter of elegance it is worth pointing out that you do not need to make use of the "large reserve" when you do step 3b. You could also put 3 light with 1 heavy agaianst 1 light and 3 reserve and treat it like measurement 2b. This construction works in general, to weigh 3N light and (3N-1)/2 heavy against (3N-1)/2 light and 3N reserve. This happens because the sum of the first N-1 powers of 3 is (3N-1)/2.
In general, this solution will solve (3N-1)/2 unknown coins with N measurements. That is only 1 worse than the solution when you have an infinite reserve, so apparently a reserve isn't as powerful as I had stated earlier. Really having a reserve just makes the solution easier to access.
Alright, next time I will post the hardest version of this puzzle that I know (though truthfully it won't be that hard, now that you have seen this solution).
No comments:
Post a Comment