多伪币问题的非适应解

Non-adaptive Solutions to the General Counterfeit Coin Problem

Dyson（The Mathematical Gazette，1946，30：231-234）提出“伪币问题”以来，已有许多不同的版本和推广，并得到广泛研究．通过拓展Born等人（Discrete Applied Mathematics，1995，61：121～131）提出的Dyson集概念，为k伪币鉴别问题和k伪币查找问题的非适应解建立了一致的数学模型，为使用数学方法处理上述两个问题的非适应解提供了便利．利用上述模型，将伪币查找问题非适应算法的可查找组合数上界缩小了近一半，并给出了一个对任何k≥1都可用的称量次数上界．

The counterfeit coin problem has been studied extensively by mathematicians and computer scientists ever since it was first raised out. Among various generalizations and variations of the original problem, the k- counterfeit-coin problem （where k is any positive integer, denoting the number of counterfeit coins presented） and its non-adaptive solutions are of interest. By extending the concept of ＂Dyson sets＂ proposed by Born etal （Discrete Applied Mathematics, 1995,61： 121- 131） , this paper gives mathematical models for non-adaptive solutions to two different versions of the k-counterfeit-coin problem （the ＂identification version＂ and the ＂search-only version＂, respectively）, converting the solution-searching problem to a mere treatment of vectors. With new models given, the upper bound of the number of all possible combinations （from which a non-adaptive scheme of w weighings suffices to determine the combination of counterfeit coins） has been reduced almost by half. An inequality providing an upper bound of the number of weighings （sufficient to identify all of the k counterfeit coins out of n coins） for any given k and n is also presented.