Scam School has been scammed! Somebody slipped Brain Brushwood some counterfeit coins, and he needs your help to separate the counterfeit coins from the real ones.

OK, this is really just the start of a puzzle, but it's a rather fascinating puzzle. Just when you think you've got the hang of the puzzle, another version can come along and make things tougher.

We'll start by jumping right in to the counterfeit coin puzzles as presented on this week's Scam School (alternative YouTube link):



All in all, not a bad pair of puzzles. For the second puzzle, I would make sure to keep the weighed coins in separate piles, of course, so I can make sure to round up all of the counterfeit coins.

Let's add a new dimension to that second puzzle, just to challenge your thinking. What if, instead of 1 bag holding all counterfeit coins, there were an unknown number of bags? As in the original puzzle, each bag holds either all real coins, each weighing exactly 1 gram, or all counterfeit coins, each weighing 1.1 grams. You still have only one weighing to find out which bags, if any, contain counterfeit coins.

If you want to try and work this out for yourself, stop reading here, as I discuss the solution below.

.

.

.

.

.

.

.

If you think about it, what you really need is a series of yes-or-no answers for each bag in a way that allows you to get this information in a single weighing. How do you achieve this?

Our old friend the binary number system comes to the rescue! If you need a quick understanding of binary numbers, watch Binary Numbers in 60 Seconds.

The solution is take 1 coin (2⁰) out of the first bag, 2 coins (2¹) out of the second bag, 4 coins (2²) out of the third bag, and so on. For each bag, you double the number of coins taken from the previous bag, all the way up to 512 (2⁹) coins taken from the 10th bag.

You'll probably note that it's easier to denote the bags as 0 through 9, instead of 1 through 10. With the bags numbered 0 through 9, we can just remember that we take 2^x coins out of bag number x.

How does taking coins out in powers of 2 help? First, consider the weight we'd get if all the coins were real. We'd have 1,023 coins weighing a total of 1,023 grams. Any weight over 1,023 grams, then, can be attributed to the counterfeit coins.

Let's say we try this out, and find that we have a total weight of 1,044.7 grams. Take away the weight of the real coins, and we're left with 21.7 grams extra. At 0.1 grams extra for each of the counterfeit coins, we now know there are 217 counterfeit coins among the 1,023 coins.

That's great, you might say, but we still don't know which bags are counterfeit. If you stop and think for a minute, you may have more information than you think. First, since you took 512 (2⁹) coins out of bag 9, the coins in that bag couldn't be counterfeit. If they were, you'd have a minimum of 512 counterfeit coins in the total.

The same argument could be made for bag 8, from which you removed 256 coins (2⁸). Still, isn't it difficult to work out all the possibilities for the remaining bags?

No, and I can explain why in a very simple way. In our everyday decimal system, how many ways are there to write the number 217? There's only one way, of course, and that's by writing a 2 in the hundreds place, a 1 in the tens place, and 7 in the ones place. The same is true for any other base, include base 2 (binary).

There's only one way to write the binary equivalent of the decimal number 217. To find out what it is, you can either do a binary conversion with the help of a tool such as Wolfram|Alpha, or, if you've been reading Grey Matters long enough, do the conversion in your head.

Done either way, the binary equivalent of 217 is 11011001, but what does this tell us? Each of these numbers represents one of the bags. To be fair and include all 10 bags, we should write it as a 10-digit binary number, 0011011001, and arrange each number under its corresponding bag like this:

9 8 7 6 5 4 3 2 1 0
0 0 1 1 0 1 1 0 0 1