Probably Counterfeit Masses

So, time for the final counterfeit masses problem. Usually I say where I first heard my puzzles from but I actually made this one up myself, with Matts help:
You have a balance scale and 41 coins. Most of the coins are identical but there might be a counterfeit among them. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. One of the 41 coins is set aside, that coin is promised not to be counterfeit. You may use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify which coin (if any) is the counterfeit coin and if it is heavy or light.

So, its essentially the same as the more counterfeit masses problem in that you don't know if the counterfeit is heavy or light, but now you don't even know if it exists. To make up for it, you are given a single coin reserve. Apparently that is enough to cancel out not knowing if the coin exists.

Probably Too Hard

Alright, well the solution to the second counterfeit coin puzzle actually isn't too hard, I've just run out of clever titles.

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).

More Counterfeit Masses

Alright, as promised, I should post the harder version of the counterfeit masses problem now. I first learned this problem from Jen:
You have a balance scale and 40 coins. 39 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. You may only use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.

The main difference here is that you do not know if the counterfeit coin is heavier or lighter, so when you make a measurement you only learn that the counterfeit coin is either "on the left and heavier" or "on the right and lighter", or things like that.

Of course, the rules for the balance scale are the same as for the original problem.

Probably Too Easy

Alright, I was going to post this earlier because the solution to the counterfeit masses problem is really easy, but then my weekend got really occupied.

So, the solution is as follows:
Split the 27 coins into 3 piles of 9. Weigh two of the piles against eachother, whichever is heavier has the counterfeit coin and if neither is heavier the coin is in the third pile. Next, split the 9 into 3 groups of 3, and weigh two of those against eachother to find which pile of 3 has the counterfeit coin. Finally weigh two of the coins in the final pile of 3 against eachother to find the coin.

Its really a simple trinary search, this problem will only trip people up if they try to do a binary search not realizing that you always gain information about the coins you don't weigh.

Its also easy to see (and prove by induction) that with N measurements you can solve the problem with 3N coins. Also this solution is optimal, you cannot do more than 3N coins with only N measurements (also provable by induction).

I'll post the more difficult problem later today.

Counterfeit Masses

So, a recent discussion with Simon caused me to remember an old puzzle I've been meaning to post for some time. There are multiple versions of this puzzle though, so I'm going to start off with the easiest one and move up. I don't know where I first learned this puzzle, I've known it since childhood:
You have a balance scale and 27 coins. 26 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it is slightly heavier than other coins. You may only use the balance scale to make 3 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.

Of course, the amount by which the counterfeit coin is heavier is imperceptible to a human, only a balance scale can tell. Using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it. The button will work 3 times and then the scale will break.

Improbable Masses

Alright, seems like its time to post the solution to the Impossible Masses problem.

First, there are two key realizations you need before you can solve the problem:
1. You may multiply the weights of all the masses by any constant and not have any effect on the puzzle
2. You may add any constant to the masses and not have any effect on the puzzle

The proofs of these are pretty simple, so I won't bother to do it.

So, first thing is that you use your power of a multiplicative constant to give all the masses integer mass (keep multiplying by denominators until you are there, basically). Next, you can use the additive constant to make one of the masses zero. Finally, you can halve all the masses as many times as it takes for there to be at least one weight with an odd mass (this step fails iff all the weights have the same mass). So, you have 11 integer masses and at least one of them is zero and at least one of them is odd.

Now, remove the zero mass, the remaining ten can be divided into two groups with the same (integer) mass. Thus, the total mass remaining must be an even number. Thus the total mass even with the zero mass included must be an even number.

Now, remove the odd mass, the remaining ten can be divided into two groups with the same (integer) mass. But, the total mass of the weights left behind must be an odd number. This is a contradiction, proving the masses must all be the same.

In the case where the masses can be real, I believe the proof goes along the same lines, but I do not actually know it myself.