[Math] Puzzle of gold coins in the bag

combinatoricsprobabilitypuzzlerecreational-mathematicssoft-question

At the end of Probability class, our professor gave us the following puzzle:

There are 100 bags each with 100 coins, but only one of these bags has gold coins in it. The gold coin has weight of 1.01 grams and the other coins has weight of 1 gram. We are given a digital scale, but we can only use it once. How can we identify the bag of gold coins?

After about 5 minutes waiting, our professor gave us the solution (the class had ended and he didn't want to wait any longer):

Give the bags numbers from 0 through 99, then take 0 coins from the bag number 0, 1 coin from the bag number 1, 2 coins from the bag number 2, and so on until we take 99 coins from the bag number 99. Gather all the coins we have taken together and put them on the scale. Denote the weight of these coins as $W$ and the number of bag with gold coins in it as $N$, then we can identify the bag of gold coins using formula $$N=100(W-4950)$$
For instance, if the weight of all coins gathered is $4950.25$ grams, then using the formula above the bag number 25 has the gold coins in it.

My questions are:

  1. How does the formula work? Where does it come from?
  2. Do we have other ways to solve this puzzle? If yes, how?
  3. If the digital scale is replaced by a traditional scale, the scale like symbol of libra or the scale in Shakespeare's drama: The Merchant of Venice (I don't know what is the name in English), then how do we solve this puzzle?

Best Answer

To understand the formula, it would be easiest to explain how it works conceptually before we derive it.

Let's simplify the problem and say there are only 3 bags each with 2 coins in them. 2 of those bags have the 1 gram coins and one has the 1.01 gram gold coins. Let's denote the bags arbitrarily as $Bag_0$, $Bag_1$, and $Bag_2$. Similarly to your problem, let's take 0 coins from $Bag_0$, 1 coin from $Bag_1$, and 2 coins from $Bag_2$. We know that the gold coins must be in one of those bags, so there are three possibilities when we weigh the three coins we removed:

Gold Coins in $Bag_0$: So the weight of the 3 coins on the scale are all 1 gram. So the scale will read 3 grams.

Gold Coins in $Bag_1$: So the weight of 1 of the coins is 1.01 grams and 2 of the coins are 2 grams. So the scale will read 3.01 grams.

Gold Coins in $Bag_2$: So the weight of 2 of the coins is 2.02 grams and 1 of the coins is 1 gram. So the scale will read 3.02 grams.

So each possibility has a unique scenario. So if we determine the weight, we can determine from which bag those coins came from based on that weight.

We can generalize our results from this simplified example to your 100 bag example.

Now for deriving the formula. Say hypothetically, of our 100 bags, all 100 coins in each of the 100 bags weigh 1 gram each. In that case, when we remove 0 coins from $Bag_0$, 1 from $Bag_1$, up until 99 coins from $Bag_{99}$, we'll have a total of 4950 coins on the scale, which will equivalently be 4950 grams. Simply put, if $n$ is our Bag number (denoted $Bag_n$), we've placed $n$ coins from each $Bag_n$ onto the scale for $n = 0, 1, 2, ... 99 $.

So the weight of the coins will be $Weight = 1 + 2 + 3 + ... + 99 = 4950$

But we actually have one bag with gold coins weighing 1.01 grams. And we know that those 1.01 gram coins must be from some $Bag_n$. In our hypothetical example, all of our coins were 1 gram coins, so we must replace the $n$ coins weighed from $Bag_n$ with $n$ gold coins weighing 1.01 grams. Mathematically, we would have: $Weight = 4950 - n + 1.01n = 4950 + .01n = 4950 + n/100$

Rearranging the formula to solve for n, we have: $100(Weight-4950) = n$, where $Weight$ is $W$ and $n$ is $N$ in your example.

I have no knowledge of an alternative answer to this puzzle, but perhaps another member's answer may be enlightening if there is. Technically speaking, you could have denoted the bags from 1 to 100 and gone through a similar process as above, but the method is still the same, so I wouldn't treat it as a new answer.

If our electric scale is replaced by a scale of libra, I don't believe it would be possible to answer this puzzle with only one measurement of weight. But again, perhaps another answer may be enlightening on that.

Related Question