Puzzle of gold coins in the bag
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:
- How does the formula work? Where does it come from?
- Do we have other ways to solve this puzzle? If yes, how?
- 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?
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.
For #1: imagine for a moment that all the coins are fake. If we took 0 coins from bag 0, 1 coin from bag 1, 2 coins from bag 2... we'd have $99\times100/2=4,950$ coins, and those 4,950 coins would weigh a total of 4,950 grams. But now, say that bag 25 were the one with real coins that are slightly heavier: 0.01 grams heavier, in fact. So the total weight of the coins is $W=4950+0.01N$, where $N$ is the number of the bag with the real coins. But -- we have the weight, not the bag number. So let's invert the equation: we want to find N given W, not the other way around.
$$\begin{align}W&=4950+0.01N\\W-4950&=0.01N\\100(W-4950)&=N\end{align}$$
For #2, aside from renumbering the bags, there isn't a different way to do this; no matter what, we have to have a different number coming from the scale for each different possible result.
For #3, you need $\lceil\log_3k\rceil$ weighings to discover the odd coin out; for 100 coins, that's 5 weighings: the first splits the coins into groups of (up to) 34; the second into groups of (up to) 12; the third into groups of (up to) 4; the fourth into groups of (up to) 2; the fifth finds it guaranteed.
Why $\lceil\log_3k\rceil$? Each use of the balance scales actually compares three different groups of coins: the one on the left scale, the one on the right scale, and the one not on the scale at all. If one of the two groups on the scale is heavier, then the gold coin is in that group; if neither, then the gold coin is in the group not on the scale. Thus, each weighing can distinguish between 3 states, and $n$ weighings can distinguish between $3^n$ states. We need an integer solution to $3^n\ge k$, thus $n\ge\log_3k$, thus $n=\lceil\log_3k\rceil$.
According to the given values, the gold coins have essentially the same weight (down to a single percent) as the base ones. Since gold is heavy this means that each gold coin is significantly smaller.
Forget about weighing and just take the bag whose coins are much smaller than the coins in the other bags.
- If all coins would have equal weight ($1.00$ gram), then the total weight of taking $0$ coins from bag $0$, $1$ coin from bag $1$, etc. would be $4950$ grams. Verify: $1 + 2 + \cdots + 99 = 4950$. To work with the example: if you take $25$ coins from bag $25$, then the total offset in weight is $0.25$ grams.
- Not that I know of.
- When the rest of the rules are the same (weighing only once), you cannot solve the puzzle.