Yep, Counterfeit Masses

So, its time for the solution to the final counterfeit masses problem. First, its worth nothing that the statement in the problem that you must determine if the counterfeit coin is heavy or light is irrelevant. Every coin in the collection must at some point step on the scale (as the counterfeit might not even be present at all), and since by the end you will know which coin was counterfeit and it was on the scale at some point, you know if it is heavy or light. Next, note that the "possible existence" of the counterfeit coin is essentially meaningless, as you can treat a problem with N coins and a guaranteed counterfeit equivalent to a problem with N-1 coins with a possible counterfeit by throwing one coin out the window. All that crap is really just to make the problem sound harder.

So we really only need to worry about having 41 coins with a guaranteed counterfeit and a 1 coin reserve and 4 weighings at our disposal. You will recall that with 4 weighings and an infinite reserve we could only do 41 coins at best, so apparently a 1 coin reserve is as strong as an infinite one.

One trick that makes this problem easy is just to always proceed as if it actually has a solution. We know that we will begin by weighing N coins against N-1 other coins plus the reserve coin (we might as well use the thing), and leave the other 41-(2N-1) coins to the side. But, if the N vs. N measurement comes out equal, we will have a "large" reserve and have to solve the problem with 42-2N coins with only 3 measurements. We know that at most then, 42-2N can be equal to 14, so N=14 (or more, but why make our lives harder). So, we have step one:

1. Weigh 14 coins against 13 coins plus the reserve coin.

If this comes out balanced, we know what to do. So, lets assume the 14 come out heavy (if they are light, just switch the notion of light and heavy), so we have 14 possibly heavy coins and 13 possibly light coins. Now, we have a reserve of 15 coins (the exact size is meaningless actually, we only need about 10 of them as we will see), and we will set aside M of our "heavy" coins and perform some measurement on the others. If that measurement comes out balanced, we will have 2 measurements left and M heavy coins, so we know that we should set M=9 at most, or we can't win if the next measurement is balanced. So, lets do that:

2. Weigh the 5 of the possibly heavy coins with 9 possibly light against the other 4 possibly light and 10 reserve, the other 9 possibly heavy coins are set aside.

If this comes out balanced, we can solve the remaining problem easily. If the 5 heavy and 9 light come out light, it must be the 9 light causing it (no heavy coins on the other side). If the 5 heavy and 9 light come out heavy, we now have 5 possibly heavy coins and 4 possibly light coins with a large reserve and 2 measurements left. Set 3 heavy aside (as if the next measurement is balanced, we can solve them with our 1 remaining measurement), and

3. Weigh 3 possibly light coins with 2 possibly heavy coins against 1 possibly light coin and 4 reserve coins, the other 3 possibly heavy coins are set aside.

If this is balanced, we know what to do. If the 3 light and 2 heavy come out light, then the 3 light caused it (no heavy on the other side). If the 3 light and 2 heavy come out heavy then we are down to 2 heavy and 1 light with one measurement left. This is easy enough:

4. Weigh one possibly light and one possibly heavy against 2 reserve coins, with the other possibly heavy coin set aside.

The cases of "balanced", "heavy", and "light" each now point to a unique coin.

It is easy to use this method to solve the (3^N+1)/2 coin case with N measurements and 1 reserve coin. So it is true that any nonzero reserve handed to you at the start is of equal strength. The technique of solving the problem by assuming the solution exists can actually get you pretty far in logic puzzles, in a few cases you can actually find a solution to a problem and not be able to prove that there actually is a solution. It works for logic puzzles because there typically is a solution, but I suppose mathematical research demands a bit of a higher level of rigor.