Optimal Algorithms for the Coin Weighing Problem with a Spring Scale

Abstract

Suppose we are given n coins out of a collection of coins of two distinct weights w0 and w1, true and counterfeit coins, respectively, where d of them are counterfeit coins. Assume we are allowed to weigh subsets of coins in a spring scale. Determine the counterfeit coins in a minimal number of weighing. This problem is equivalent to the following learning problem: Given a linear function f = xi1 + xi2 + + \cdots + xid, where $1 \leq i$1 < i2 < · · · < i$d \leq n$ and a substitution oracle of values in the domain $\{0,1\}^n$ to f. Find f with minimal number of substitution queries. In this paper we give the first optimal1. (in the number of weighing or substitutions) polynomial time adaptive algorithm that determines the counterfeit coins. We then extend our algorithm to the following more general coin weighing problems with a spring scale: Suppose we are given n coins out of a collection of coins of unknown integer weights. De- termine the weight of each coin in a minimal number of weighing. We give an optimal adaptive polynomial time algorithm for this problem. This algorithm is based on a new optimal adaptive algorithm for reconstructing bounded weight vectors in polynomial time. This solves the general problem of learning any linear function with bounded integer coefficient in polynomial time with optimal number of substitution queries. To the best of our knowledge all the algorithms in this paper are the first optimal polynomial time adaptive algorithms for the problem of coin weighing in a spring scale.