Optimal non-adaptive solutions for the counterfeit coin problem

2015/02/17 by Cuong Nguyen, C. Thach Nguyen, Nguyen, C. Thach
Computer Science · Mathematics · #Mathematical Dynamics and Fractals #Optimization and Search Problems #cs.DM #math.HO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1502.04896

arxiv created 2015/02/17 · arxiv updated 2015/02/23

Abstract

We give optimal solutions to all versions of the popular counterfeit coin problem obtained by varying whether (i) we know if the counterfeit coin is heavier or lighter than the genuine ones, (ii) we know if the counterfeit coin exists, (iii) we have access to additional genuine coins, and (iv) we need to determine if the counterfeit coin is heavier or lighter than the genuine ones. Moreover, our solutions are non-adaptive.

Related

• Solution to the Counterfeit Coin Problem and its Generalization
• An improved lower bound on the counterfeit coins problem
• A note on the counterfeit coins problem
• Counting Counterfeit Coins: A New Coin Weighing Problem
• Some Results on the Counterfeit Coins Problem