A NEW COMPETITIVE ALGORITHM FOR THE COUNTERFEIT COIN PROBLEM

Consider a set of coins where each coin is either of a heavy type or a light type. The problem is to sort the coins (according to the type) by minimizing the number of weighings on a balance. The case that only one coin, called a counterfeit, has a different weight than the other s is a classic mathematical puzzle. Later works study the case of more than one counterfeit, but the number of counterfeits is always assume d known. Recently, Hu and Hwang gave an algorithm that does not depend on the knowledge of the number of counterfeits, and yet performs unif ormly well whatever that number turns out to be in the sample consider ed. Such an algorithm is known as a competitive algorithm and the unif orm guarantee is measured by its competitive constant. In this paper w e give a new and simple competitive algorithm whose competitive consta nt improves the existing one by a ratio of 2/3.