## Problem of the Week 1155## Find the GoldA 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," © Copyright 2012 Stan Wagon. Reproduced with permission.
2 October 2012 |