Sometimes Optimal One-Stage Balance Scale Searching with Errors

Abstract

We spec ifi ca ll y g ive a one-stage and o ne erro r-correc tin g solution 10 the wellknow n ba lance sca le prob lem for a single coun1 erfe i1 co in. Our method can be ge nera li zed to the one-stage mullipl e e rro r- correcting balance sc ale prob lem fo r a single co unterfe it coin. Our so lution for the o ne e rror-correcting case is optimal in many instances . In pani c ul ar, for the cases of 12 and 39 coins, our one-stage and one e rror-correc ting solutions use six and seven ba lance sca le comparisons respecti ve ly . Using the sphere pack ing bound , we show 1ha1 th ese so luti ons are optima l.