这只是一类数学趣题,典型的问题被称为“ counterfeit coin problem ”和 “ odd ball ( or coin) problem ",一直有人在试图设计出更巧妙便捷的解题方法,但该问题本身并不具有在生活和其他学科中存在大量应用的特征,目前对该问题的解法也不具有较为重大的理论意义,不足以形成专门的数学研究分支。
解的规模也不会随着问题规模的增大发生组合爆炸, 因此这类问题不属于组合优化问题。
《蚁迹寻踪及其他数学探索》(第12章针对12硬币问题提出一种非常简便的新解法,不过推荐看英文原文(和豆瓣那个评论意见相反,我认为该书中文翻译相当糟糕),这里有这一章的英文原文:在这个网页下面,还可以找到多篇研究该类问题的其它文章,比如 , 。用天平称量k次,可以确保找出个球中的目标球,不能确保找出个球中的目标球 这个引理很简单,归纳法易证略过 引理2:有n个未知球和足量标准球,且目标球是重还是轻未知。
() 归纳法证明: 1,k=2时 若有个未知球ABCD和标准球E,称量A+B/C+E 如果A+B=C+E则D是目标球,称量DE即可知道D轻D重 如果A+B>C+E,称量A/B,如果A>B则A重,如果A<B则B重,如果A=B则C轻 如果A+B<C+E类似上一种情况,略去 若有个未知球ABCDE和标准球若干,由于两次称量的结果只能有种无法分辨A重/A轻/B重/B轻……/E重/E轻等10种情况,故无法确保找出目标球 2,假定k=j时成立,试证k=j+1时成立 若有个未知球和若干标准球,分为三组,数量分别为AC组各个球,B组个球,取标准球F,称量A+F与B 若A+F=B,则目标球在C组中,ABF都是标准球,根据归纳假设,可以j次称量找出目标球,共计j+1次称量 若A+F≠B,则目标球在AB组中,且AB组共个球,CF都是标准球,A组比B组少一个,根据引理2,可以j次称量找出目标球,共计j+1次称量 故有标准球时天平称量j+1次可以确保找出个未知球中的目标球 ←下界证毕 若有个未知球与若干标准球,则共有种状态(每个球轻或重),j+1次称量只有种结果无法分辨 ←上界证毕 最后是原命题 若有个未知球,分为ABC三组,数量分别为个球 称量AB组,若A=B,则目标球在C组中且AB组均为标准球,根据引理3,可以在k-1次称量内找出目标球,共称量k次 若A>B,则目标球在AB组中且C组均为标准球。