You have a sack of coins of three types: brass, silver and gold. You know that the majority of the coins are gold, though they’ve been painted and partially hollowed so that you can’t actually determine the type of a particular coin. Fortunately, you have a machine into which you can insert two coins and the machine will tell you whether the two coins are of the same type or different types.
Your task is to locate a gold coin.
You will compare the coins in “passes” with each coin not being compared more than once in a pass. In a pass, every coin can be a member of a comparison or not, but any particular coin can’t be part of more than one comparison during the pass. Your goal is to minimize the number of passes required to be sure that you locate a single gold coin.
You should be able to describe how many passes (at most) your solution will require rather than the number of passes increasing arbitrarily with the number of coins that turn out to be in the bag.