Problem of the Week 1155
Find the Gold
A sack has 1155 coins of three types: brass, silver, and gold. A majority of the coins (at least 578) are gold, but the coins are disguised so there is no way of distinguishing one type from another.
You have a machine that accepts two coins and tells you whether or not they are made of the same material.
An algorithm to identify a gold coin is said to have "depth k" if each coin is inserted at most k times into the machine.
Find an algorithm of minimal depth that produces a gold coin.
Source: The Math Factor; this is a variation of a problem discussed in Alonso, Reingold, and Schott's "Determining the majority," Information Processing Letters 47 (1993) 253-255.
© Copyright 2012 Stan Wagon. Reproduced with permission.
2 October 2012