A generalized algorithm for solving n coins problem

摘要

Eight coins problem is a well-known problem in mathematics as well as in computer science. In this problem eight coins are given, say A, B, C, D, E, F, G, and H, and we are told that only one is counterfeit (or false), as it has a different weight than each of the others. We want to determine which coin it is, making use of an equal arm balance. At the same time we want to identify the counterfeit coin using a minimum number of comparisons and determine whether the false coin is heavier or lighter than each of the remaining. In this paper, we develop algorithms for solving the counterfeit coin problem for any given number n of coins. The first algorithm is in essence based on the existing classical solution for the eight coins problem (with slight modification) for larger values of n, where n is a power of two beyond eight, as two and four being base cases. Then we develop an algorithm for solving n coins problem, where n is even but not power of two, i.e., the numbers are six, ten, 12, 14, 18, 20, etc. At the end, we have extended the same to solve the counterfeit coin problem for odd number of coins as well.