Hosted by The Math Forum

# Find the Gold

MacPOW Home || Math Forum POWs || Search MacPOW

## Solution

The task can be accomplished in merely two passes, which is minimal. We can credit reader Stephen Morris (England) with a nice solution, which I copy below. The comments at his mathfactor site contain some interesting variations of the problem.

The key point is that most of the coins are gold. We can throw away coins with abandon as long as we know that no more than half of them are gold. Most of the remaining coins will still be gold.

The choices for the first pass are entirely arbitrary. We simply group coins into arbitrary pairs.

If a pair is different, then we discard it on the basis that we are discarding at least as many non-gold coins as gold coins. We will still have a majority of gold coins. This leaves us with only matched pairs.

For the second pass, we can take one coin from one of these matched pairs and compare it to a coin from another matched pair. If they are different, we discard both pairs: we know that we are discarding at least as many nongold coins as gold coins, so we will still have the majority of the coins being gold.

Now we have groups of four coins which are matched. Each group has two coins which have not been compared in the second pass. Again we take a coin from each group of four and compare it to a coin from another group of four. Again we throw away groups which do not match.

Now we have groups of eight coins which are matched. Each group has two coins which have not been matched in the second pass. Etc., etc.... We can keep matching groups until we run out of groups of the same size. Since the size of each group is a power of two, the largest group will be all gold.

We have used only two passes.