Gold Coins Puzzle

You might have stubled on this puzzle from different sources. Some of you will have found it online, others in a book. There are variations of the puzzle but they’re more or less the same.

With that said, here’s the problem description:

You are given 10 bags of gold coins. Nine bags contain coins that each weigh 10 grams. One bag contains all false coins that weigh one gram less. You must identify this bag in just one weighing. You have a digital balance that reports the weight of what is placed on it.

Solution Link to heading

The main constraint is:

You must identify this bag in just one weighing

At face value the description didn’t seem to give out any hints, but upon further inspection I found this useful

One bag contains all false coins that weigh one gram less.

What this meant is that if we could identify one bad coin we could also identify all of them with certainty.

My strategy is as follows:

Step 1.: pick one coin from each bag and mark it with either a letter or a number indicating its relative position to the rest. If letters are chosen and you start from letter $ a $ then the first coin you take out will be marked with this letter; the second will be marked with $ b $, and so forth until letter $ j $. Similarly if you decided to use numbers, you’d start from 1 and go to 10.

If marking isn’t allowed for example because no marker/pen is provided, then we will have to use memory. I find memorising letters easier than numbers so I would go with letters.

Step 2.: place the ten coins on the balance in the same order we took them from their respective bags. For the sake of simplicity we assume that placing of coins appens simultaneously, as not to break the constraint of the exercise, i.e. we are given a robotic arm or some other device that can put all coins on the balance at the same time. The key here is that the ordering is preserved on the balance.

Step 3.: we pick up one coin at a time from the balance and monitor the weight decrease. Depending on the ordering of the initial selection, the bad coin could be anywhere from position $ a (1st) $ to $ j (10th) $.

Step 4.: the moment we pick up one coin that causes the weight drop by 9 grams instead of 10, we also identify the bag from which it came from, and solve the problem.

This runs in $ O(n) $ time. In the best case we identify the bad coin on the first pickup, but in the worst case we need to traverse the entire set of $ n $ coins.

I’m not 100% confident this is the optimal way but it is workable. Also its validity depends on what is meant by “one weighing”. I interpreted one weighing as the physical act of placing the coins on the balance, not taking them off of it. If the word measurement had been used instead of weighing, then I would’ve opted for a different strategy.