两伪币的搜索问题  

Searching for two counterfeit coins

作　　者：武晓辉[1] 李胜家[1] 

机构地区：[1]山西大学数学科学学院,太原030006

出　　处：《运筹学学报》2016年第4期102-108,共7页Operations Research Transactions

基　　金：国家自然科学基金(No.61174082)

摘　　要：考虑两伪币的搜索问题:给定外观相同的n个硬币,其中有两个比较重的伪币,通过等臂天平在尽可能少的称量次数下去找出两个伪币.L^((2))(n)为最坏情况下找到两伪币的最小称量步数.对于任意的n≥2,满足log_3(_2~n)]≤L^((2))(n)≤[log_3(_2~n)]+1.猜想信息理论下界均可达.通过一个新的方法扩大了满足信息理论下界的n的取值范围.The following weighting problem is considered： determine two counterfeit coins which are heavier than good coins in a set of n coins of the same appearance using only an equal arms balance. Let L（2） （n） denote the minimum number of weighings necessary when exactly two ofn coins are known to be defective. For all n≥2, it satisfies log_3（_2-n）]≤L-（（2））（n）≤[log_3（_2-n）]＋1. It was conjectured that the lower bound is always achieved. In this paper, using a novel algorithm, we improve on the range of n for which the lower bound is reached.

关 键 词：组合搜索 组测试 称重问题 两伪币 

分 类 号：O229[理学—运筹学与控制论]