I love logic puzzles, and I recently found this excellent collection from Professor Rustan Leino of Microsoft: http://research.microsoft.com/en-us/um/people/leino/puzzles.html
I highly recommend you check them out! Anyway, a friend of mine asked that I try to solve and explain one of those puzzles in particular, ‘Weighing piles of coins‘. Here’s how Rustan puts it:
There are two kinds of coins, genuine and counterfeit. A genuine coin weighs X grams and a counterfeit coin weighs X+delta grams, where X is a positive integer and delta is a non-zero real number strictly between -5 and +5. You are presented with 13 piles of 4 coins each. All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit. You are given a precise scale (say, a digital scale capable of displaying any real number). You are to determine three things: X, delta, and which pile contains the counterfeit coins. But you’re only allowed to use the scale twice!
First Weighing
My first instinct was to figure out how many coin piles I could leave out of the first weighing. Often in these puzzles, not measuring has as much informational value as measuring. Say you weigh two coins each from nine piles and get an exact multiple of 18 as your weight. You can then be sure that one of the four piles you didn’t weigh is the counterfeit, and use your second weighing to find it.
There’s a problem, though – this puzzle is hard. Not only are you required to find the offending pile of coins, you must also determine X and Δ. If you measure two coins each from eleven piles and get something like 44 (a perfect multiple of 22, the number of coins you’ve measured) you then know that X=2 and one of the two unweighed piles is counterfeit. In order to be sure to find Δ, you must then weigh at least one coin from each of those piles. Best case scenario, you weigh one coin from pile A and four from pile B. Your result will be 5X+(Δ or 4Δ). Unfortunately, Δ can be arbitrarily small so if the measurement is off by 5 or less you will be unable to determine which pile is responsible. If you get something like 7, Δ could be 2 or .5 and there’s no way to tell which. The upshot of this is that the requirement to identify Δ means that the most piles you can leave out of the first weighing is one.
We have twelve piles left to deal with, and we want to get as much information as possible out of this first weighing. The best way to do this is to weigh 1, 2, 3 and 4 coins from each set of three piles:
This is a total of 3*(1+2+3+4), or 30 coins. We expect them to weigh 30*X+(an offset), with that offset being made up of either Δ, 2Δ, 3Δ or 4Δ depending on which group the counterfeit pile is in. Let’s refer to this total offset from the first measurement as δ. If we get an exact multiple of 30, we know that the thirteenth pile is counterfeit and can simply weigh a single coin from it to determine Δ (after determining X by dividing our weight by 30). I’ll be using this sort of diagram for the rest of this post, to represent the columns of coin piles which we’ve taken different numbers of coins from in this first weighing.
So how big can δ be? Since Δ can be anything from -5 to 5, if one of the piles we weighed four of is bad we could be dealing with up to 20 grams of δ. Our job now is to use the second weighing to determine X, Δ and the counterfeit pile. This first weighing will narrow down the possible values of X to two integers, depending on the nearest two multiples of 30 to our measured weight. Since our result will always fall between two neighboring multiples of 30, let’s just look at a generalized interval of possible outcomes:
Let’s assume that X=1 for a moment. Since we have either 1, 2, 3 or 4 counterfeit coins in the 30 we weighed, our weight could come out anywhere between 30 and 50. The teal lines indicate which amounts of counterfeit coins could account for each observed weight. If the weight is anywhere from 30-35, we have no idea how many counterfeit coins are involved. If the weight is higher than 45, then it could only be one of the piles we weighed four of. That is, unless X=2.
Since Δ can also be negative, this is the full picture. It looks pretty gnarly – how can we use our final weighing to differentiate between all of these possibilities? I’m going to single out and provide solutions for the most difficult possible cases, and try to show that any other outcomes are just easier versions of those. If you look closely, you can see that there are only five locations with four possible values of Δ. Since the plot is symmetrical, there are really only three:
Case A is between 30 and 35 (or 55 and 60), case B is exactly 40 (or 50), and case C is exactly 45. Let’s start with case A.
Second Weighing
Case A
We know X for sure, because we’re too far from the next multiple of 30 for the counterfeits to have thrown us off. Any of the twelve piles we’ve weighed could be the counterfeit, and Δ must either equal δ, δ/2, δ/3 or δ/4 depending on how many coins of the bad pile we weighed:
Our goal now is to carefully select how many of each of these piles to include in our second weighing, such that we expect a unique weight to result from each possible pile’s being counterfeit. For example, it would be bad to include one coin from a pile in the left column if we also had two from one in the second column, three from one in the third or four from one in the fourth. All of these groups of coins would result in a weight offset of δ, and we wouldn’t be able to tell which of them had caused it. As before, we can leave one single pile out of the weighing – if there is no weight anomaly, we will know that this is the counterfeit pile. We will then be able to deduce Δ by virtue of knowing which column that pile belonged in.
The thirds column is pretty easy, as any amount of each pile save three gives a unique value. Let’s include 2, 3 and 4 from the left-hand column, as this only precludes us from including four from the next column over. We’ll add 1, 2 and 3 from that column then. This leaves us able to include 1, 3 and zero of each of the fourths piles!
The functionality of this setup may not be immediately obvious, but if we calculate out the expected values of δ for each pile it’s clear that each one provides a unique outcome:
My notation isn’t perfect, but I hope it’s clear – I’m showing the expected value of the δ in the second weighing in units of the δ from the first weighing. This solves Case A!
Case B
If δ is exactly 10 grams, we know that the piles we weighed a single coin from are legitimate. The piles we took 2, 3 or 4 coins from are suspect. Further, if one of the four-coin piles is counterfeit it’s possible that X=2 rather than 1 (and Δ is -5). These four possible cases compose a point of maximal difficulty for us. Luckily, we can solve it with a very similar approach to Case A. We can disregard the one-coin piles, but we need to consider both possible cases for the four-coin piles separately:
This may look a little confusing – remember, we’re not considering the piles we took single coins from. Since δ=10, we know that Δ would be 5 for the piles we took two coins from and 10/3 for the piles we took three from. The piles we took four coins from have split possibilities. Either X=1 and Δ=2.5, or X=2 and Δ=-5. We need to choose an arrangement of coins to include in the second weighing so that every one of these possibilities gives a unique outcome. The 10/3 pile can again contribute 1, 2 and 4. This leaves us with the twos and fours. Remember that the fours are a single column of three piles, so we can only pick one number per pile despite the requirement to come up with six different possible outcomes. Also note in the case of Δ=-5, our base measurement will be 60 and the counterfeits will take us down the scale from there. Because of this, three coins with Δ=-5 would give the same result as 3 coins from the left-hand column (45). Two coins would also give the same result as four from the left-hand column. This means that only one of these columns can have 2 and 4, and the other can have a 3. Let’s give 1, 2 and 4 to the leftmost column, and 0, 1 and 3 to the rightmost.
Again, notice that the two columns on the right are really just one column in superposition of possible X values. It’s okay to measure no coins from one of those piles because we’d be able to tell from the base weight what X is and therefore determine Δ. So what are our expected δs?
Remember that the rightmost possibility leads to a base weight of 30, minus 5 grams per each counterfeit coin. Since these are all unique outcomes, we’ve solved Case B! Take a deep breath, there’s only one case left to deal with…
Case C
If δ is exactly 15, we know that the counterfeit pile is one from the three-coin or four-coin columns. In this case, each of these columns has two possible values of X:
The three-coin piles can be 15/3 or -15/3, and the four-coin piles can be 15/4 or -15/4. The same issues with equality exist here as above – we can’t take three coins from the left pile because we’d expect 45 from both possible values of X and Δ. We also can’t take both 2 and 4 coins. To avoid these problems, we’ll take 0, 1 and 2. The right piles only have this issue with four coins, since we’d expect 45 from both again (we don’t want to repeat the first weighing). Since 0 is already taken by a pile, we’ll have to use 1, 2 and 3.
And that will give us…
Phew! That’s all of the hardest cases dealt with. If the first weighing results in anything between them, we’ll just be dealing with a simpler situation. For example, if we get 46 instead of 45 – this would be an easier version of Case C, where we already know that the leftmost column (X=1 and Δ=5) isn’t counterfeit. We can simply run the second weighing as before and still get a solution.
If you’ve stayed with me through all of this, thanks for reading! I realize that this is a pretty in-depth treatment, but I had fun making it and I hope it will be useful for anyone who’d like a walk-through of the solution.
Keep puzzling!
Within Riesen 