Problem of the Week 1155

Find the Gold

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

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.

[View the solution]